COMMENT ⊗   VALID 00021 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	.SS(Becoming an Expert,,P120:)
C00015 00003	As you may have discovered, the real difficulty in 
C00032 00004	It %6is%* possible to write a directly recursive reversing function
C00036 00005	.SEC(Applications of LISP,Applications)
C00046 00006	.SS(Examples of LISP Applications,,P255:)
C00053 00007	.SS(Differentiation,differentiation,P41:)
C00065 00008	%1
C00070 00009	.<<abstracting from rep>>
C00084 00010	.SS(Tree Searching)
C00100 00011	.SS(Data Bases,,P220:)
C00126 00012	.SS(Algebra of Polynomials,,P264:)
C00138 00013	.GROUP
C00142 00014	.SS(Evaluation of Polynomials,,P2:)
C00146 00015	.<<PROBLEMS ON POLY EVAL >>
C00148 00016	.CENT(More on polynomial evaluation)
C00176 00017	Let's go through a complete evaluation of %2B%* of {yon(P124)}.
C00181 00018	.CENT(Time to take stock)
C00189 00019	.<<AND THE GREAT MOTHERS>>
C00190 00020	.SS(Another Respite)
C00200 00021	.<<PROVING PROPERTIES>>
C00209 ENDMK
C⊗;
.SS(Becoming an Expert,,P120:)
.begin "exp"
.BEGIN "foo" TURN ON "←";
.FP
We have already traced the development of a few LISP algorithms, and we
have given a few  programming hints. It is time to 
reinforce these tentative starts with a more intensive study of the
techniques for writing good LISP programs.
This section will spend a good deal of
time showing different styles of definition, giving hints about how to
write LISP functions, and increasing your familiarity with LISP.
For those of you who are impatiently waiting to see some %6real%* applications
of this programming language, we can only say "be patient".
The next chapter %6will%* develop several non-trivial algorithms, but
what we must do first is improve your skills, even at the risk of
worsening your disposition.

.BEGIN "xx" GROUP;
First some terminology is appropriate:
the style of definition which we have been using is called
%2⊗→definition by recursion↔←%*. 
The basic components of such a definition are:
.PT24;
.BEGIN INDENT 10,10;
%21.%* A basis case: what to compute as value for the function in
one or more particularly simple cases. A basis case is frequently referred to
as a termination case.
.END
.FP
%2REC%*
.BEGIN INDENT 10,10;
%22.%* A general case: what to compute as value for a function, given
the values of one or more previous computations with that function.
.END
.PT24
.END "xx";
.FP
You should compare the structure of a %2REC%*-definition of a function
with that of an %2IND%*-definition of a set (see %2IND%* on {yon(P117)}).
Applications of %2REC%*-definitions are particularly useful in computing
values of a function defined over a set which has been defined by an
%2IND%*-definition. 
For example, assume that we have defined a set %dA%* using %2IND%*  then a typical
algorithm for computing a 
function  %df%*  over %dA%* would involve two parts: first, 
an indication of how to compute
%df%* on the base domain of %dA%*, and second, given values for some elements
of %dA%* say %da%41%1,#...,%da%4n%1,
use %2IND%* to generate a new element %da%1; then specify the value of %df(a)%*
as a function of the known  values of %df(a%41%*)%1,#...,# %df(a%4n%*)%1.
That is exactly the structure of %2REC%*.

.P119:
.BEGIN GROUP;
Here is another attribute of %2IND%*-definitions: Suppose we have defined a 
set %dA%* using %2IND%*, and we wish to prove that a certain property 
%2P%* holds for every element of %dA%*. We need only show that:
.BEGIN INDENT 10,10;
.PT24
%21.%*  %2P%* holds for every element of the base domain of %dA%*.
.END
.FP
%2PRF%*
.BEGIN INDENT 10,10;
%22.%* Using the
technique we elaborated in defining  the function %df%* above, if we
can show that %2P%* holds for the new element perhaps relying on proofs
of %2P%* for sub-elements, then we should have a convincing argument that
%2P%* holds over %6all%* of %dA%*.
.END
.PT24
.END
.FP
This proof technique is a generalization of a common technique
for proving properties of the integers. In that context it is called
mathematical induction.

We are seeing an interesting parallel between inductive definitions
of sets, recursive definitions of functions, and proofs by induction.
As we proceed, we will exploit various aspects of these  interrelationships.
However our task at hand is more mundane: to develop facility at
applying %2REC%* to define functions over the %2IND%*-domains 
of symbolic expressions, %dS%*,  and of sequences, %dSeq%*.

First let's verify that the functions we have
constructed so far do indeed satisfy %2REC%*.
Recall our example of %3equal%* on {yon(P1)}. 
The basis case involves a calculation on members of %d<atom>%*;
there we rely on %3eq%* to distinguish between distinct atoms.
The question of equality for two non-atomic S-exprs was recast as a
question of equality for their %3car%*s and %3cdr%*s. But that too,
is proper since the constructed object is 
manufactured by %3cons%*, and %3car%* and %3cdr%* of that object
select the components.

Similar justification for %3length%* on {yon(P118)} can be given.
There the domain is %dSeq%*. The base domain is the empty sequence, and
%3length%* is defined to give %30%* in that case. The general case in the
recursion comes from
the %2IND%*-definition of a sequence.⊗↓Note ({yon(P114)}) that we didn't give
an explicit %2IND%*-definition, but rather a set of BNF equations.
The reader should supply the explicit definition.← 
Given a sequence %2s%*, we made a new sequence by adding a sequence element
to the front of %2s%*. Again the computation of %3length%* parallels
this construction, saying that the length of this new sequence is
one more than the length of the sequence %2s%*.

For a more traditional  example consider the factorial function, n!.
.PT24
.NL
%21.%*##The function is defined for non-negative integers.
.NL
%22.%*##The value of the function for 0 is 1.
.NL
%23%*.##Otherwise the value of n! is n times the value of (n-1)!.
.PT24
.GROUP;
It should now be clear how to write a LISP program for the factorial function:

.BEGIN CENTERIT;SELECT 3;
.P20:
.BOXA
←fact[n] <= [eq[n;0] → 1; %et%* → times[n;fact[sub1[n]]]] ⊗↓%3times%1 is 
a LISP function  which performs multiplication, and
 %3sub1%1 subtracts %31%1 from its argument.←
.BOXB
.END
.APART
.FP
The implication is that it is  easier to compute (n-1)! than
to compute n!. But that too is in accord with our construction of 
the integers using the successor function.

These examples are typical of LISP's recursive definitions.
The body of the definition is a conditional expression; the first few
branches involve  special cases, called %2⊗→termination conditions↔←%*.
Then  the remainder of the conditional covers the general case-- what to
do if the argument to the function is not one of the special cases.

Notice that %3fact%* is a partial function, defined only for non-negative
integers. 
When writing or reading LISP definitions pay particular attention to the
domain of definition and the range of values produced. 
The following general hints should also be useful:
.PT24
.NL;
%21%*.##Is the algorithm to be  a LISP function or predicate? This information can be used to
double-check uses of  the definition. Don't use a predicate where a 
S-expr-valued function is expected; and don't use an S-expr-valued function
where a list-value is expected.
.NL
%22%*.##Are there  restrictions on the argument positions? 
For example, must some of the arguments be truth values? Similar
consistency checking as in %21%* can be done with this information.
.NL
%23%*.##Are the termination conditions compatible with the restrictions
on the arguments?  If it is a recursion on lists, check for the empty
list; if it is a recursion on arbitrary S-exprs, then check for the
appearance of an atom.
.NL
%24%*.##Whenever a function call is made within the definition, are all
the restrictions on that function satisfied?
.NL
%25%*.##Don't try to do too much. Try to be lazy. There is usually a very simple
termination case. 
If the termination case looks messy, there is probably something wrong with your
conception of the program.
If the general case looks messy, then write some  subfunctions
to perform the brunt of the calculation. 
.PT24
.FP
Apply the  suggestions when writing any subfunction. When you are
finished, no function will do very much, but the net effect of all the
functions acting in concert is a solution to your problem. That is
part of the mystique of recursive programming.


As you may have discovered, the real difficulty in 
programming is writing  your own programs. But who says programming
is easy? LISP at least makes some of your decisions easy. Its
constructs are particularly frugal. So far there is only %6one%* way to write
a non-trivial algorithm in LISP: use recursion. The structure of the program
flows like that of an inductive argument. Find the right induction hypothesis
and the inductive proof is easy; find the right structure on which to recur 
and recursive programming is easy. It's easier to begin with unary functions;
then there's  no question about which argument 
is to be decomposed. The only decision 
is how to terminate the recursion.  If the argument is an S-expr
we typically terminate on the occurrence of an atom. If the argument is a
list, then terminate on %3(#)%*. If the argument is a number then terminate on zero.

.GROUP;
Consider a slightly more complicated arithmetical example, the 
⊗→Fibonacci sequence↔←: 0,#1,#1,#2, 3,#5,#8,#...#. This sequence can be
characterized by the following recurrence relation:

.BEGIN CENTERIT;
.BOXA
.GROUP
←f(0) = 0
←f(1) = 1
←f(n) = f(n-1)+f(n-2) 
.BOXB
.APART
.END
.APART

.GROUP
.fp
The translation to a LISP function is easy:

.BEGIN TABIT2(16,27);SELECT 3;GROUP;
.BOXA
\fib[n] <=\[eq[n;0] → 0;
\\ eq[n;1] → 1;
\\ %et%* → plus[fib[sub1[n]];fib[sub1[sub1[n]]]]]
.BOXB
.END
.fp
where %3plus%* is a representation of the mathematical function  %3+%*.
.APART

A few additional points can be made here. Notice that an evaluation
scheme may imply many duplicate computations.  For example,
computation of %3fib[5]%* requires the computation of %3fib[4]%* and %3fib[3]%*.
But within the calculation of %3fib[4]%* we  again calculate %3fib[3]%*,
etc.  It would be nice if we could restructure the definition of 
%3fib%* to stop this extra computation.⊗↓An alternative solution
is to supply a different evaluation scheme which might be able to remember
previously calculated results.#⊗↑[Got#74]↑.← Since we %6do%* wish to run
programs on a machine we should give some attention to efficiency.⊗↓For 
those readers with some programming experience, 
the solution may appear  easy: assign the
partial computations to temporary variables.  The problem here is that
our current subset of LISP doesn't contain assignment.← 

.GROUP;
We will define another function, called %3fib%9'%1, on three variables %3x%*,
%3y%*, and %3n%*. The variables, %3x%* and %3y%*, will be used to carry
the partial computations. Consider:

.BEGIN TABIT2(17,33);SELECT 3;CENTERIT;
.GROUP
.BOXA
←fib%41%*[n] <= fib%9'%*[n;0;1]

%1where:%3\fib%9'%*[n;x;y] <=\[eq[n;0] → x;
\\ %et%* → fib%9'%*[sub1[n];plus[x;y];x]]
.BOXB
.APART
.END
.APART
.FP
This example is complicated enough to warrant 
closer examination. The initial call,
%3fib%41%*[n]%1, has the effect of calling %3fib%9'%1 with %3x%* initialized to
%30%* and with %3y%* initialized to %31%*. The calls on %3fib%9'%1 within the body
of the definition, say the i%8th%* such recursive call, has the effect
of saving the i%8th%* Fibonacci number in %3x%* and the i-1%8st%* in %3y%*.
.GROUP;
For example:

.BEGIN TABIT2(25,35);SELECT 3;GROUP;
.BOXA
\fib%41%*[4] \= fib%9'%*[4;0;1]
\\= fib%9'%*[3;1;0]
\\= fib%9'%*[2;1;1]
\\= fib%9'%*[1;2;1]
\\= fib%9'%*[0;3;2]
\\= 3
.BOXB
.END
.APART
.FP
Functions like %3fib%9'%1, used to help %3fib%41%1, are called "help#functions"
or %2⊗→auxiliary#function↔←s%1; variables like %3x%1 and %3y%1 in %3fib%9'%1
are called %2⊗→accumulators↔←%1#(⊗↑[Moor#74]↑), 
since they are used to accumulate the partial computations.
The technique of using auxiliary functions and accumulators can 
also be applied to the
factorial example. When viewed computationally, the resulting definition 
will be more efficient, though
the gain in efficiency is not as apparent  as that in the Fibonacci
example.⊗↓The %3fib%41%1 example improves efficiency mostly 
by calculating fewer intermediate results.
The gain in the %3fact%41%1 example is involved with the machinery
necessary to actually execute the program: the run-time
environment, if you wish. We will discuss this when we talk about
implementation of LISP in {yonsec(P107)}. The whole question of: "what is
efficient?" is open to discussion.←
.GROUP;
.FP
Thus:

.BEGIN TABIT1(10);SELECT 3;GROUP;CENTERIT;
.P21:
.BOXA
←fact%41%*[n] <= fact%9'%*[n;1] 

%1where:%3←fact%9'%*[n;x] <= [eq[n;0] → x; %et%* → fact%9'%*[sub1[n];times[n;x]]]
.boxb
.APART
.END
.APART;
.FP
It appears  that the pairs %3fact, fact%41%1 and
%3fib, fib%41%1 are equivalent. Perhaps we should prove that this is so.
We presented the  crucial ideas for the proof in the discussion on {yon(P119)}
concerning %2IND%*, %2REC%* and %2PRF%*.
We shall examine the question of proofs of equivalence in {yonss(P15)}.

.GROUP;
Auxiliary functions are also   applicable to LISP functions
defined over S-exprs:

.BEGIN tabit1(10);SELECT 3;group;
.P19:
.BOXA
\length[n] <= [null[n] → 0; %et%* → add1[length[rest[n]]]] ⊗↓add1[x] <= x+1←
.PT18
\length%41%*[n] <= length%9'%*[n;0]
.PT2
%1where:##%3length%9'%*[n;x] <= [null[n] → x; %et%* → length%9'%*[rest[n];add1[x]]]
.PT2;
%1Again, it appears that %3length%1 is equivalent to %3length%41%1.
.boxb
.APART
.END
.APART

So far our examples have either been numerical or have been predicates.
Predicates only require traversing existing S-exprs; certainly  we will
want to write algorithms which build new S-exprs.  Consider the problem
of writing a LISP algorithm to  reverse a list %3x%*. There is a simple informal
computation: take elements from the front of %3x%*  and put them
onto the front of a new list %3y%*. Initially, %3y%* should be  %3(#)%* and
the process should terminate when %3x%* is empty. 
.GROUP;
For example, reversal of the list %3(A B C D)%1 would produce the sequence:

.BEGIN SELECT 3; TABIT2(32,49);
\x\y
\(A B C D)\( )
\(B C D)\(A)
\(C D)\(B A)
\(D)\(C B A)
\( )\(D C B A)
.END
.BOXB
.APART
.fp
What follows is  %3reverse%*, where we use a sub-function
%3rev%9'%1 to do the hard work and perform the initialization with 
the second argument to %3rev%9'%1.

.BEGIN CENTERIT;SELECT 3;GROUP;
.P97:
←reverse[x] <= rev%9'%*[x;( )]
.PT2
←rev%9'%*[x;y] <= [null[x] → y; %et%* → rev%9'%*[rest[x];concat[first[x];y]]]
.BOXB
.APART
.END

.P16:
.FP
This %3reverse%* function builds up the new list 
by  %3concat%*-ing
the elements onto the second argument of %3rev%9'%*%1. Since %3y%* was initialized
to %3(#)%* we are assured that the resulting construct will be a list.
We will
see a "direct" definition of the reversing function in a moment.

The development of an algorithm which constructs new objects
may not always be so straightforward. Suppose we require 
 a LISP function named ⊗→%3append%*↔← of two list arguments, %3x%* and %3y%*,
which is to return a new list which has %3x%* appended onto the front of %3y%*.
For example:

.BEGIN CENTERIT;SELECT 3; GROUP;
.boxa
.EQ1(20);
\append[(A B D);(C E)] = (A B D C E)
\append[A;(B C)] %1 = %9B%1 since %3A%1 is not a list.
\%3append[(A B C);( )] = append[( );(A B C)] = (A B C)
.boxb
.END
.APART
.END
.FP
%3append%* is a partial function; it should be defined by recursion,
but recursion on which argument?  If either argument is %3(#)%*
then the value given by %3append%* is the other argument. 
The next simplest case is a one-element
list; if exactly one of %3x%* or %3y%* is a singleton how does that help us
discover the recurrence relation for appending? It doesn't help much if %3y%*
is a singleton; but if %3x%* is a singleton, then %3append%* could give:
.PT18
←%3concat[first[x];y]%* as result 
.PT18
.FP
So recursion on %3x%* is likely. The definition now follows.

.P22:
.BOXA
←%3append[x;y] <= [null[x] → y; %et%* → concat[first[x];append[rest[x];y]]].%1
.BOXB
.FP
Notice that the construction of the result is a bit more obscure than
that involved in %3reverse%*. The construction has to "wait" until
we have seen the end of the list %3x%*. For example:

.BEGIN  SELECT 3;GROUP;
.turN ON "\"; NOFILL; TABS 1,32,41,48,55
.KRK; 
.BOXA
\append[(A B C);(D E F)] \= concat[A;append[(B C);(D E F)]]
.pt2
\\= concat[A;concat[B;append[(C);(D E F)]]]
\\= concat[\A;
\\\concat[\B;
\\\\concat[\C;
\\\\\append[( );(D E F)]]]]
.pt2
\\= concat[A;concat[B;concat[C;(D E F)]]]
.pt2
\\= concat[A;concat[B;(C D E F)]]
.pt2
\\= concat[A;(B C D E F)]
.pt2
\\= (A B C D E F)
.BOXB
.APART
.END
.FP
We are assured  of constructing a list here because %3y%* is a list
and we are %3concat%*-ing onto the front of it. LISP functions
which are to construct list output by %3concat%*-ing %6must%*  concatenate onto  
the front of an existing %6list%*. That list may be either
non-empty or the empty list, %3(#)%*. 
This is why the termination condition on a list-constructing function,
such as the following function, %3dotem%*,
returns %3(#)%*.


.BEGIN SELECT 3;TABIT1(18);
.BOXA
dotem[x;y] <= [\null[x] → ( );
\%et%* → concat[cons[first[x];first[y]];dotem[rest[x];rest[y]]]]
.BOXB
.END
.FP
The arguments to %3dotem%* are both lists assumed to contain the same
number of elements. The value returned is to be a list of dotted pairs; the 
elements of the pairs are the corresponding elements of the input lists. 

Note  the use of both %3concat%* and %3cons%*: %3concat%*
is used to build the final list output; %3cons%* is used to build the
dotted pairs. Now if we  had written %3dotem%* such that it knew
about our representation of lists, then %6both%* functions would have been
%3cons%*. The definition would not have been  as clear.


.BEGIN CENTERIT;SELECT 1;
.GROUP;
Look at a computation as simple as %3dotem[(A);(B)]%*. This will involve
.BOXA
←%3concat[cons[A;B];dotem[( );( )]] 
.BOXB
.APART
.GROUP;
.FP
%1Now the evaluation of %3dotem[( );( )]%1 returns our needed %3( )%*, giving
.BOXA
←%3concat[cons[A;B];( )] = concat[(A . B);( )] = ((A . B))
.BOXB
.END
.FP
If the termination condition of %3dotem%* returned anything other than
%3(#)%* then the list-construction would "get off on the wrong foot"
and would not generate a  list.

As promised on {yon(P16)}, here is a "direct" definition of %3reverse%*.

.BEGIN SELECT 3;TABIT1(17);GROUP;
.BOXA
.P23:
reverse[x] <=\[null[x] → ( );
\ %et%* → append[reverse[rest[x]];concat[first[x];( )]]] 
.BOXB
.END
.FP
This reversing function is not as efficient as the previous one.
Within the construction of the reversed list the %3append%* function
is called repeatedly. You should evaluate something like %3reverse[(A B C D)]%*
to see the difficulty.
.END "foo"

It %6is%* possible to write a directly recursive reversing function
with no auxiliary functions, no functions other than the primitives, and
with not much clarity. We shall persist  because it is a good example of
 discovering the general case of the recursion by careful
consideration of examples. Let us call the function %3rev%*.

We consider the general case first, and
postpone the termination conditions  until later. Consider, for example,
%3rev[(A#B#C#D)]%*. This should evaluate to %3(D#C#B#A)%*. How can we
construct this list by recursive calls on %3rev%*? 
Assume %3x%* has value %3(A#B#C#D)%*.
Now note that %3(D#C#B#A)%* is the
value of %3concat[D;(C#B#A)]%*. Then %3D%* is %3first[rev[rest[x]]]%* (it is also
%3first[rev[x]]%* but that would not help us since the recursion must reduce
the complexity of  the argument).

.GROUP;
How can we get %3(C#B#A)%*?## Well:
.BEGIN TABIT2(21,30);GROUP;SELECT 3;
.BOXA
\(C B A)\= rev[(A B C)]
.pt2
\\= rev[concat[A;(B C)]] 
.pt2
\\    %1(we are going after %3rest[x]%* again,
\\        but first  we can get %3A%1 from %3x.
.pt2
\\= rev[concat[first[x];(B C)]]
.pt2
\\= rev[concat[first[x];rev[(C B)]]]
.pt2
\\= rev[concat[first[x];rev[rest[(D C B)]]]]
.pt2
\\= rev[concat[first[x];rev[rest[rev[rest[x]]]]]]
.BOXB
.END
.APART;
.BEGIN SELECT 3;tabit3(30,37,48);
.BOXA
%1That is, %3rev[x] %1looks like%3\concat[\first[rev[rest[x]]];
\\rev[concat[\first[x];
\\\rev[rest[rev[rest[x]]]]]]]
.BOXB
.END

%1
.FP
Now, the termination conditions are simple. First %3rev[(#)]%* gives %3(#)%*.
But notice that the general case which we just constructed has %6two%*
%3concat%*s.  That means the shortest list which it can make is of length two.
So lists of length one are also handled separately: the reverse of such a list
is itself.
Thus the complete definition should be:

.BEGIN SELECT 3;GROUP;TABIT3(13,25,36);
.BOXA
rev[x] <= [\null[x] → ( );
\null[rest[x]] → x;
\%et%* → concat[\first[rev[rest[x]]];
\\rev[concat[\first[x];
\\\rev[rest[rev[rest[x]]]]]]] ]
.BOXB
.END

We have only hinted at the issue of efficiency in computation. The question of
efficiency involves deeper questions of the evaluation mechanisms. We will
return to these issues after we have discussed the LISP evaluation
scheme more completely.
.REQUIRE "PROB5.PUB" SOURCE_FILE;

.end "exp"
.SEC(Applications of LISP,Applications)
.BEGIN EP;
"...All the time I design programs for nonexisting machines and add:
`if we now had a machine comprising the primitives here assumed, then the job is
done.'
.EP
 ... In actual practice, of course, this ideal machine will turn out not to exist, so
our next task --structurally similar to the original one-- is to program the
simulation of the "upper" machine.... But this bunch of programs is written
for a machine that in all probability will not exist, so our next job will be
to simulate it in terms of programs for a next lower level machine, etc.,
until finally we have a program that can be executed by our hardware...."
.END
.PT24;
.BEGIN TURN ON "→";

→E. W. Dijkstra, ⊗↑[Dij#72]↑########
.END
.PT24;PT24;PT2;

.SS(Introduction,,P287:)
.FP
There are several ways of interpreting this remark of Dijkstra.
Anyone who has programmed at a level
higher than machine language has experienced the phenomenon. The act of
programming in a high-level language is that of writing algorithms for
a nonexistent high-level machine. Typically  however, the changes of 
representation from machine to machine are all done automatically: from
high-level, to assembly language, and finally to hardware instructions.

A related view of Dijkstra's remark involves our
discussions of abstract data structures and algorithms.
We express our algorithms and data structures in terms of abstractions
independent of how they may be represented in a machine; indeed we can
use the ideas of abstraction %6regardless%* of whether the formalism
will find a representation on a machine. This use of abstraction is the
true sense of the programming style called "structured programming".
We will see in this chapter how this programming style is a natural 
result of writing representation-independent LISP programs.

As we have previously remarked, we will see a close relationship
between the structure of an algorithm and the structure of the data.
We have seen this already on a small scale: list-algorithms 
tend to recur "linearly"
on %3rest%* to %3(#)%*; S-expr algorithms tend to recur "left-and-right" on
%3car%* and %3cdr%*, finally decomposing the expression to atoms.
Indeed, the instances of control structures appearing in an algorithm 
typically parallel
the style of inductive definition of the data structure which the
algorithm is examining.⊗↓The ideas 
sketched here have more formal explanations in algebraic
notions; see ⊗↑[Hen#75]↑.← 
.GROUP;
If a structure is defined as:

.BEGIN CENTERIT;
.BOXA
←%eD%1 ::= %eD%41%1 | %eD%42%1 | %eD%43%1  
e.g.← <seq elem> ::= <indiv> | <seq>
.BOXB
.END
.FP
then we can expect to find a conditional expression whose
predicate positions are filled by the recognizers for the
%eD%4i%1's. 
.APART
.GROUP
If the structure is defined as:
.BEGIN CENTERIT;
.BOXA
←%eD%1 ::= %eD%41%1 ...  %eD%41%1  
e.g.←  <seq> ::= %2(%*<seq elem>%2,%* ..., <seq elem>%2)%*
.BOXB
.END
.FP
that is, a homogeneous sequence of elements, then we will have a 
"linear" recursion like that experienced in list-algorithms.⊗↓ Indeed
there are other forms of control like iteration or 
%3lit%* ({yon(P133)})
which are related to such data structures.← 
.APART
.GROUP;
Finally if the structure is defined with a fixed number of components as:
.BEGIN CENTERIT;
.BOXA
←%eD%1 ::= %eD%41%1 %eD%42%1 %eD%43%1... %eD%4n%1
e.g. ←   <sexpr> ::= %3(%*<sexpr> . <sexpr>%3)%*
.BOXB
.END
.FP
then we can expect  occurrences of selector functions to
extract the components from the structure.⊗↓You may have
noticed that we are therefore dealing with essentially "context-free" abstract
data structures; i.e., those generated by context-free grammars. See#⊗↑[Hop#69]↑.←
.APART;

Thus a data-structure algorithm tends to "pass off" its
work to subfunctions which will operate on the components of the data
structure. Thus if a structure of type %eD%1 is made up of components 
of types 
%eD%41%1,
%eD%42%1,
%eD%43%1, and 
%eD%44%1, then the structure of an algorithm %3f%* operating on %eD%*
typically involves calls on subfunctions %3f%41%1 through %3f%44%1 to
handle the subcomputations. Each %3f%4i%1 will in turn break up its %eD%4i%1.
Thus  the type-structure of the call on %3f%* would be: 

.BEGIN CENTERIT;
.BOXA
←%3f[%eD%3] = g[%3f%41%3[%eD%41%3];%3f%42%3[%eD%42%3];%3f%43%3[%eD%43%3];%3f%44%3[%eD%44%3]]
.BOXB
.END
.FP
This is the essence of level-wise programming: we write %3f, f%41%*,#...#,#f%44%1
independently of the representation of their data structures.
%3f%* will run provided that the %3f%4i%1's are available. 
As we write the %3f%4i%1's we will probably invoke computations on
components of the corresponding %eD%4i%1. Those computations are in turn
executed by subfunctions which we have to write. This process of
elaboration terminates when all subfunctions are written and all
data structures have received concrete representations. In LISP this means
the lowest level functions are expressed in terms of LISP primitives
and the data structures are represented in terms of S-exprs. Thus at the highest
level we tend to think of a data structure as a class of behaviors; 
we don't care about the internal mechanisms which implement that behavior.
At the lowest
level, machine-language routines  simulate %6one%* of many possible representations.

This process of elaboration of abstract algorithm and abstract data structure
may modify the top-level definition of %3f%*. 
In reality, implementation considerations
may effect some earlier decisions and require replanning of an earlier strategy.
At that time the complete plan should be re-examined; local  modifications may
have global repercussions.
A programming style is not a
panacea; it is no substitute for clear thinking.
It only helps control the complexity of the programming process.
.SS(Examples of LISP Applications,,P255:)
.BEGIN "XX20" TURN ON "←";
.FP
The next few sections will examine some non-trivial problems
involving  computations on data structures.  We will describe
the problem intuitively, pick an initial representation for the
problem, write the LISP algorithm, and in some cases "tune" the
algorithm by picking "more efficient" data representations.

The examples share other important characteristics: 
.PT24
.NL
%21.%*##We examine the problem domain and attempt to represent its elements 
as data structures.
.NL
%22.%*##We reflect on our (intuitive) algorithm and try to express it 
as a LISP-like data-structure manipulating function.
.NL
%23.%*##While performing %21%* and %22%*, we might have to modify some of
our decisions. Something  assumed to be structure might better be represented
as algorithm, or some algorithm might be better repesented as a data structure.
.NL
%24.%*##When the  decisions are made, we evaluate the LISP function on a 
representation of a problem.
.NL
%25.%*##We reinterpret the data-structure output as an answer to our problem.
.PT24
.FP
Pictorially in terms of LISP:

.BEGIN GROUP;TABIT1(35);preface 0 mills;
.P46:
.BOXA
informal  => LISP function\|
algorithm\|
\| evaluation
\|========> interpret 
\|            S-expr output as answer
\|
domain    => S-expressions\|
.BOXB
.END

Whenever we write computer programs,  whatever language we use,
we always go through a similar representation problem. 
The process is more apparent in a higher-level language like 
FORTRAN or ALGOL, and is most noticeable in a language like LISP which
primarily deals with data structures.

When we deal with numerical algorithms, the representation problem
has usually been settled in the transformation from real-world situation
to a numerical problem. One has to think more explicitly about
representation when we deal with structures like arrays or matrices. 
We are encoding
our information in the array. But the preceding diagram occurs 
within the machine, even for strictly non-structured
numerical calculation.

.BEGIN GROUP;TABIT1(30);preface 0 mills;
.BOXA
numerical => machine 
algorithm     instructions\|
\|  execution
\|========> interpret 
\|        binary number as answer
\|
numbers => binary\|
            representation
.BOXB
.END
.FP
The encodings are done by the input routines. The result of the execution is
presented to the external world by the output routines.

However, when  we come to data-structure computations,
the representation problem really
becomes apparent.  We have to think more about what 
we are doing since we lack certain preconceptions or intuitions about
such computations. More importantly,  we are trying to represent
actual problems %6directly%* as machine problems. We do not attempt to
first analyze them into a complex mathematical theory, but
try to express our intuitive theory directly as 
manipulations of data-structures.
This is a different kind of thinking, due wholly to the advent of 
computers.  Indeed the field of computation has expanded so much
as to make the term  "computer" obsolete. "Structure processor" is more
indicative of the proper level at which we should view "computers".

We have already seen a simple example of the representation  problem
in the discussion of list-notation beginning in {yonss(P100)}.


.BEGIN GROUP;TABIT1(35);preface 0 mills;
.BOXA
sequence\|
 algorithm => LISP function\|
\|  evaluation
\|=========> interpret 
\|              S-expr result as answer.
\|
sequence \|
 expression => S-expression\|

.END

The following sections deal with representation of complex data structure problems
in LISP. 
.end "XX20"
.SS(Differentiation,differentiation,P41:)
.begin "diff";
.BEGIN "CC20"
.FP
This example will describe a rudimentary differentiation
routine for polynomials in several variables.  
We will develop this algorithm through several stages. We will begin
by doing a very direct, but representation-dependent, implementation.
We will encode polynomials as special LISP lists and will express the 
differentiation
algorithm as  a LISP program operating on that representation.
When this program is completely specified we will then scrutinize it,
attempting to see just how much of the program and data structure
is %6representation%1 and how much is essential to the 
algorithm.

You should recognize two facts about the differentiation algorithm for polynomials:
first, the algorithm operates on forms (or expressions) 
as arguments and returns forms
as values. 
Previously discussed algorithms have operated on simple values and produced
simple values. The differentiation algorithm takes expressions as arguments
and produces a new expression as value.
Second, you should realize that the  algorithm for differentiation is
%6recursive%1.  The question of differentiating a sum is reduced
to the ability to differentiate each summand.  Similar relationships 
hold for products, differences, and powers.
  There must be some termination
conditions.
Differentiation of a variable, say %3x%*, with respect to %3x%* is defined to be 
the number one;
differentiating a constant, or a variable not equal to %3x%* with
respect to %3x%* gives a result of zero.  
This begins to sound like  the %2IND%*-definitions of sets
(in this case the set of polynomials) and the associated %2REC%*-definitions
of algorithms (in this case differentiation of polynomials).
If this %6is%* the mold into which our current problem fits, then we must
give an inductive definition of  our set of polynomials.
Though polynomials can be arbitrarily complex, involving the operations of addition,
multiplication, negation, and exponentiation,  their general format is very simple
if they are described in our LISP-like notation where the operation 
precedes its
operands. We assume that binary plus, times, and exponentiation are 
symbolized by +, *, and ↑; we will
write %3+[x;2]%* instead of the usual infix notation  %3x+2%*.
The general term for this LISP-like notation is %2⊗→prefix notation↔←%*.

Here are some examples of infix and prefix representations:
.BEGIN TABIT2(30,45);
.GROUP
.BOXA
\%2infix\prefix
%3
.pt2
\x*z+2y\+[*[x;z]; *[2;y]]
\x*y*z\*[x;*[y;z]]
%1
.BOXB
.APART
.END

We  now give an inductive definition of the set of polynomials
we wish to consider. The definition will involve an inductive definition
of terms.

.BEGIN GROUP;
.PT24
.NL
%21.%*##Any term is a polynomial.
.NL
%22.%*##If p%41%* and p%42%* are polynomials then the "sum"
of p%41%* and p%42%* is a polynomial.
.END

.GROUP
.FP
where:
.NL
%21.%*##Constants and variables are terms.
.NL
%22.%*##If t%41%* and t%42%* are  terms then the "product" 
of t%41%* and t%42%* is a term.
.NL
%23.%*##If t%41%* is a variable and t%42%* is a constant then 
"t%41%* raised to the t%42%*%8th%1 power" is a term.
.NL;
%24.%*##If t%41%* is a term then "minus" t%41%*  is a term.
.PT24
.APART
.END "CC20"
.GROUP;
.FP
We  now give a BNF description of the above set using the syntax of prefix notation:


.BEGIN TABIT1(13);GROUP;
.P149:
.BOXA
<poly>\::= <term> | <plus>[<poly>;<poly>]
.PT2
<term>\::= <constant> 
\::= <variable> 
\::= <times>[<term>;<term>] 
\::= <expt>[<variable>;<constant>]
\::= <minus><term>
.PT2
<constant>\::= <numeral>  
.PT2
<plus>\::= + 
.PT2
<times>\::= * 
.PT2
<expt>\::= ↑
.PT2
<minus>\::= -
.PT2
<variable>\::= <identifier>
.BOXA
.END
.APART;

It is easy to write recursive
algorithms in LISP; the only problem here is that the domain and
range of LISP functions is S-exprs, not the polynomials.
We need  to represent arbitrary polynomials as S-exprs.
We will do the representation
in lists rather than  S-exprs.
.GROUP;
Let %eR%* be a function mapping polynomals to their representation such
that 
a variable is mapped to its uppercase counterpart in the 
vocabulary of LISP atoms. Thus:
.BEGIN CENTER;
.BOXA
%eR%f(%1<variable>%f)%1#=#<literal atom> 
.BOXB
.END
Let constants (numerals), be just the LISP numerals;
these are also respectable LISP atoms.  Thus:
.BEGIN CENTER;
.BOXA
%eR%*%f(%1<numeral>%f)%1#=#<numeral> 
.BOXB
.END
.APART
.FP
We have now specified a representation for the base domains of the
inductive definition of our polynomials. It is time to develop the
termination cases for the recursive definition of differentiation.

.GROUP
We know from differential calculus that
if %3u%* is a constant or a variable then:
.BOXA
.BEGIN TABIT2(10,20);
\d%3u%*/d%3x%* =\1 if %3x = u
\\%10 otherwise
.END
.BOXB
.APART

.GROUP
.FP
We
will represent the d-operator as a binary  LISP function named %3diff%*.
The application, d%3u%*/d%3x%* will be represented as %3diff[u;x]%*.
Since constants and variables are both represented as atoms,
we can check for both of these cases by using the predicate %3isindiv%*.
Thus a representation of the termination cases might be:

.BEGIN TABIT2(10,20);
.P182:
.BOXA
\%3diff[u;x] <= [isindiv[u] → [eq[x;u] → 1; %et%* → 0] ... ]%*
.BOXB
.END
.APART
.FP
Notice we write the abbreviation, %3isindiv%* instead of %3isindiv%4r%1.
You should be a bit wary of our definition already: %3diff[1;1]%* will
evaluate  to %31%*.


Now that we have covered the termination case, what can be done for the
representation of the remaining class of terms and polynomials? 
That is, how should we represent sums and products?

First, we will represent the operations *, +, -, and ↑ as atoms:

.BEGIN tabit1(33);GROUP;
.BOXA
\%eR%*%f(%1 + %f)%1 = %3PLUS%1
\%eR%*%f(%1 * %f)%1 = %3TIMES%1
\%eR%*%f(%1 - %f)%1 = %3MINUS%1
\%eR%*%f(%1 ↑ %f)%1 = %3EXPT%1
.BOXB
.END

We will now extend the mapping %eR%* to occurrences of binary operators by mapping
to three-element lists:
.BOXA
.BEGIN CENTERIT;
←%eR%*%f(%3 %9α%3[%9β%41%3;%9β%42%3] %f)%1 = %3(%eR%f(%9α%f)%3, %eR%f(%9β%41%f)%1, %eR%f(%9β%42%f)%3) 
.END
.BOXB
.BEGIN CENTERIT;GROUP
Unary applications will result in two-element lists:
.BOXA
←%eR%*%f(%3 %9α%3[%9β%3] %f)%1 = %3(%eR%f(%9α%f)%3, %eR%f(%9β%f)%3) 
.BOXB
.END

.BEGIN CENTERIT; GROUP;

%1For example:←%eR%f(%3 +[x; 2] %f)%1 =  %3(PLUS X 2)%*
.GROUP
For a more complicated example, the polynomial 
%3
.BOXA
←x%82%* + 2yz + u
%1
.BOXB
.APART
will be translated to the following prefix notation:
.BOXA
%3
←+[↑[x;2]; +[*[2;*[y;z]]; u]]     ⊗↓%1This is messier than it really needs to 
be because we assume that + and * are binary. You should also notice
that our %eR%*-mapping is applicable to a larger class of expressions
than just <poly>. Look at %3(x#+#y)*(z#+#2).←  
.BOXB
.FILL
%1
.FP
From this it's easy to get the list form:
.NOFILL
%3
.BOXA
←(PLUS (EXPT X 2)  (PLUS (TIMES 2 (TIMES Y Z)) U))
.BOXB
%1
.FILL
%1
.BEGIN TABIT3(10,28,39);CENTERIT;
.GROUP
.once fill
Now we can complete the differentiation algorithm for + and *.  We know:
.BOXA
\d[%3f + g%*]/d%3x%* = d%3f/%*d%3x + %*d%3g%*/d%3x.
.BOXB
%1
.APART

.GROUP
.FP
Expressing this phrase as part of %3diff%1,
.pt2
we would see:#####%3u = %eR%f(%3 f + g %f)%1  = %3(PLUS, %eR%f(%3 f %f)%3, %eR%f( %3g %f)%3)%1
.PT2
.FP
where:←%3second[u] = %eR%f( %3f %f)%1### and, %3###third[u] = %eR%f(%3 g %f)%1         ⊗↓As we intimated earlier, 
we have entered an unwise course here.
We have tied the algorithm for symbolic differentiation to a specific 
representation for polynomials. Believing that much can 
be learned from seeing mistakes, we will use that  representation, and
on {yon(P74)} we will examine our decision.←
.APART


.GROUP;
.FILL
.FP
The result of differentiating %3u%* is to be a new list of three
elements:
.PT24
.NL
%21.%1##The symbol %3PLUS%*.
.NL
%22.%1##The effect of %3diff%* operating %eR%f( %3f %f)%1
.NL
%23.%1##The effect of %3diff%* operating %eR%f( %3g %f)%1
.APART
.PT24

.GROUP
.FP
Thus another part of the algorithm:

%3
.ONCE CENTER
.BOXA
eq[first[u];PLUS] → list [PLUS; diff[second[u];x];diff[third[u];x]] 
.BOXB
%1.


d[%3f*g]%*/d%3x%* is defined to be %3f* %1d%3g%*/d%3x + g *%1d%*f/%1d%*x%1.
.BOXB
.APART


.GROUP
.FP
So here's another part of %3diff%*:
%3
.BEGIN TABIT3(10,35,39);CENTERIT;
.BOXA
\eq[first[u];TIMES] →\list[\PLUS; 
\\\list[TIMES; second[u];diff[third[u];x]];
\\\list[TIMES;third[u];diff[second[u];x]]]
.BOXB
.END
.SELECT 1
.APART

.GROUP;
.FP
Finally, here's an example. We know:
.BOXA
←d[%3x*y + x]%*/d%3x = y + 1%*
.BOXB
.END
.GROUP
.FP
Try:
%3
.BEGIN TABIT3(10,17,21);
.BOXA
diff [(PLUS (TIMES X Y) X); X]
\= list[PLUS; diff[(TIMES X Y); X];diff[X;X]]
\= list[\PLUS; 
\\list[\PLUS; 
\\\list[TIMES; X; diff[Y;X]];
\\\list[TIMES; Y; diff[X;X]]];
\\diff[X;X]]

\= list[\PLUS;
\\list[\PLUS;
\\\list[TIMES; X ;0];
\\\list[TIMES; Y;1]];
\\1 ]
.BOXB
.APART
\=(PLUS  (PLUS (TIMES X 0) (TIMES Y 1)) 1)
.BOXB
.END
%1
which can be interpreted as:
.BOXA
%3
←x*0 + y*1 + 1  
%1
.BOXB
.FP
Now it is clear that we have the right answer; it is equally clear that
the final representation leaves much to be desired. There are obvious
simplifications which  would  have done before we would
consider this output acceptable. This example is a
particularly simple case for algebraic simplification. We can easily
write a LISP program to perform simplifications like those expected here:
like replacing %30*x%1 by %30%*, and %3x*1%* by %3x%*. But the general
problem of writing simplifiers, or indeed of recognizing 
what is a "simplification", is quite difficult.
A whole branch of computer science has grown up around 
symbolic and algebraic manipulation of expressions. One of the
crucial parts of such an endeavor is a sophisticated simplifier.
For more details and examples of the power of such systems see
⊗↑[Hea#68]↑, ⊗↑[MAC#74]↑, or ⊗↑[Mos#74]↑.

.END
.<<abstracting from rep>>
.CENT(Points to note)

.SELECT 1;
.FP
This problem of representation is typical of data structure
algorithms regardless of what language you use.  That is,
once you have decided what the informal algorithm is, pick a
representation which makes your algorithms clean. Examine the interplay between
the algorithm and the representation, and continue to examine your decisions
as you refine your method.
In {yonss(P264)} we will see a
 series of representations, each becoming more and more "efficient"
and each requiring more "knowledge" being built into the algorithm.
The remainder of this section will reexamine our  representations in
the differentiation  algorithm.

.GROUP
First, here is the complete %3diff%1 algorithm for  + and *:
%3
.BEGIN 
.TURN ON "\";NOFILL;TABS 15,43,45,49;KRK;
.BOXA
diff[u;x] <=\[isindiv[u] → [eq[x;u] → 1; %et%* → 0];
\ eq[first [u]; PLUS] → list\[PLUS; 
\\ diff[second[u]; x];
\\ diff[third[u]; x]];
\ eq[first[u]; TIMES] → list[\PLUS; 
\\\list[\TIMES; 
\\\\second[u];
\\\\diff[third[u]; x]];
\\\list[\TIMES; 
\\\\third[u];
\\\\diff[second[u]; x]]];
\ %et%* → %9B%*]  ⊗↓%1The element %9B%1 is not strictly part of LISP.←
.BOXB
.END
.APART
.select 1;
.P74:
.FP
As we mentioned earlier, the current manifestation of %3diff%* encodes too
much of our particular representation for polynomials. The separation
of algorithm from representation is beneficial from at least two standpoints.
First, changing representation should have a minimal effect on the structure
of the algorithm; but %3diff%* knows that variables are represented as atoms
and knows that a sum is represented as a list whose %3first%*-part is %3PLUS%*.
Second, readability of the algorithm suffers greatly.
How much of %3diff%* really needs to know about the representation and
how can we improve the readability of %3diff%*?

The uses of %3first%*, %3second%*, and %3third%* are not 
particularly mnemonic.⊗↓However,  they are
more readable than %3car-cdr%*-chains.←  We used
%3second%* to get the first argument to a sum or product and used %3third%*
to get the second.
We used %3first%* to extract the operator.
However %3first%1, %3second%1, and %3third%1 select components of sequences;
they know nothing about polynomials. We want to refer to polynomials
as abstract data structures.

.GROUP;
.fp
Let's define the selectors:

.BEGIN tabit1(35);sELECT 3;group;
.BOXA
\op[x] <= first[x]
.PT2
\arg%41%*[x] <= second[x]
.PT2
\arg%42%*[x] <= third[x]
.BOXB
.END
.APART
.GROUP
.FP
Then %3diff%* becomes:

.BEGIN TABIT3(15,42,46);select 3;
.GROUP
.BOXA
diff[u;x] <=\[isindiv[u] → [eq[x;u] → 1; %et%* → 0];
\ eq[op[u]; PLUS] →   list\[PLUS; 
\\ diff[arg%41%*[u]; x];
\\ diff[arg%42%*[u]; x]];
\ eq[op[u]; TIMES] → list\[PLUS; 
\\ list\[TIMES; 
\\\ arg%41%*[u];
\\\ diff[arg%42%*[u]; x]];
\\ list\[TIMES; 
\\\ arg%42%*[u];
\\\ diff[arg%41%*[u]; x]]];
\ %Et%* → %9B%*]
.BOXB
.APART
.END
.APART
.FP
Still, there is much of the representation present. Recognition of variables
and other terms can be abstracted. We need only
recognize when a term is a sum, a product, a variable or a constant.
  To test for the occurrence of a numeral we shall assume
a unary LISP predicate called %3numberp%* which returns %et%* just in the case
that its argument is a numeral.
Then,
in terms of the current  representation, we could define such recognizers and
predicates as:

.BEGIN "XX21" CENTERIT; SELECT 3;group;
.boxa
.EQ1(26);
\issum[x] <= eq[op[x];PLUS]
\isprod[x] <= eq[op[x];TIMES]
\isconst[x] <= numberp[x]
\isvar[x] <= [isindiv[x] → not[isconst[x]]; %et%* → %ef%*]
\samevar[x;y] <= eq[x;y]
.PT18
.END
.END "XX21"
.GROUP;
.FP
Now we can rewrite %3diff%* as:

.BEGIN TABIT3(15,33,37);select 3;
.GROUP
.BOXA
diff[u;x] <= \[isvar[u] → [samevar[x;u] → 1; %et%* → 0];
\ isconst[u] → 0;
\ issum[u] →  list[\PLUS; 
\\diff[arg%41%*[u]; x];
\\diff[arg%42%*[u]; x]];
.pt2
\ isprod[u] → list[\PLUS; 
\\list[\TIMES; 
\\\arg%41%*[u];
\\\diff[arg%42%*[u]; x]];
\\list[\TIMES; 
\\\arg%42%*[u];
\\\diff[arg%41%*[u]; x]]];
\ %et%* → %9B%3]
.BOXB
.APART
.END
.APART;
.FP
Readability is certainly improving, but the representation is still
known to %3diff%*.
When we build the result of the sum or product of derivatives we use
knowledge of the representation.
It would be better to define:
.BEGIN "XX23" CENTERIT;SELECT 3;group;
.EQ
makesum[x;y] <= list[PLUS;x;y]
.EQ1(24);
\makeprod[x;y] <= list[TIMES;x;y]
.END
.END "XX23"
.PT18
.GROUP;
.FP
Then the new %3diff%* is:

.BEGIN TABIT3(15,39,50);select 3;
.GROUP
.p101:
.BOXA
diff[u;x] <=\[isvar[u] → [samevar[x;u] → 1; %et%* → 0];
\ isconst[u] → 0;
\ issum[u] → makesum[\diff[arg%41%*[u]; x];
\\diff[arg%42%*[u]; x]];
\ isprod[u] → makesum[\makeprod[\arg%41%*[u];
\\\diff[arg%42%*[u]; x]];
\\makeprod[\arg%42%*[u];
\\\diff [arg%41%*[u]; x]]];
\ %et%* → %9B%3]
.BOXB
.APART
.END
.APART
.FP
In the process,
%3diff%* has become much more understandable and, more importantly, the details
of the representation have been relegated to subfunctions. Changing
representation simply requires supplying different subfunctions. No changes
need be made to %3diff%*. There has only been a slight decrease in efficiency.
The termination condition in the original %3diff%* is a bit more succinct,
but  speaking precisely it was incorrect. The gain in independence
far outweighs the slight efficiency consideration.
Looking back, first we abstracted the selector 
functions: those which selected components; next we abstracted the recognizers:
the predicates indicating which kind of term was present; finally we modified
the constructors: the functions which make new terms.
These three components of programming: selectors, recognizers, and constructors,
will appear again on {yon(P75)} in a discussion of McCarthy's abstract syntax.

The %3diff%* algorithm is much more abstract now, 
in the sense that the representation
of the domain and the representation of the functions and predicates which
manipulate that domain have been extracted out.⊗↓To be 
particularly precise, our references to %30%1 and %31%1
should really be %3mkconst[0]%1 and %3mkconst[1]%1, signifying
the functions which make constants.← This is our %9r%*-mapping
again; we mapped the domain of <poly>'s to lists and mapped the
constructors, selectors, and recognizers to list-manipulating functions.
Thus the data types of the arguments %3u%* and %3x%* are <poly> and <var>
respectively, %6not%* list and atom. To  stress this point we should make one more
transformation on  %3diff%*. We have frequently said that there
is a substantial parallel between a data structure and the algorithms which
manipulate it. Paralleling the BNF definition of <poly> on {yon(P149)}, we 
write:

.BEGIN TABIT2(15,39);select 3;
.GROUP
.BOXA
diff[u;x] <=\[isterm[u] → diffterm[u;x];
\ issum[u] → makesum[\diff[arg%41%*[u]; x];
\\diff[arg%42%*[u]; x]];
\ %et%* → %9B%3]
.APART
.BOXB
.end
.BEGIN TABIT3(19,43,54);select 3;
.GROUP
diffterm[u;x] <=\[isconst[u] → 0;
\ isvar[u] → [samevar[x;u] → 1; %et%* → 0];
\ isprod[u] → makesum[\makeprod[\arg%41%*[u];
\\\diff[arg%42%*[u]; x]];
\\makeprod[\arg%42%*[u];
\\\diff[arg%41%*[u]; x]]];
\ %et%* → %9B%3]
.BOXB
.APART
.END

.GROUP;
.FP
To satisfy our complaint of {yon(P182)} that %3diff[1; 1]%1 gives a defined
result, we should also add:

.BEGIN TABIT2(10,22);SELECT 3;GROUP;
.BOXA
\diff%9'%*[u; x] <= [isvar[x] → [ispoly[u] → diff[u; x]]; %et%3 → %9B%3]
.BOXB
.END
.APART
.FP
Finally, notice that our abstraction process has masked the order-dependence
of conditional expressions. Exactly one of the recognizers will be satisfied
by the form  %3u%*.



.CENT(Problems)
.PT24
.NL
1.##Extend the version of %3diff%* of your choice to handle differentiation
of powers such as  %3↑[x; 3]%1.
.NL
2.##Extend %3diff%* to handle unary  minus.
.NL
3.##Extend %3diff%1 to handle differentiation of the trigonometric functions,
%3sin%1 and %3cos%1 and their composition with polynomials.
For example it should handle %3sin%82%3x#+#cos(x%83%3#+#5x#-2)%1.
.NL
4.##Write an algorithm to handle integration of polynomials.
.end "diff"
.SS(Tree Searching)
.fp
A natural application of LISP's recursive power occurs
in  tree searching  algorithms.  These algorithms are the heart of
programs which play games.
A ubiquitous feature of sophisticated game playing is "a strategy".
In  a simple game, for example tic-tac-toe, an optimal strategy may 
be easily computable.
In games like checkers and chess, the algorithmic approach would require
enormous computational power; heuristic  methods are applied
to reduce the  computational requirements. 

The heart of  this strategy formation is often
a tree structure.  That tree will have nodes representing "possible moves".
In a single-person game, the  evaluation of the tree will result in
a "best move"; any move that wins. In a two-person game we must be more careful;
the branching structure will represent %6both%1 your moves and those
of the opponent, and the position evaluation must
take that into account: "Now if I move here, then  my opponent will move 
there,#...#."

The  tree-structured data and recursive programming style of LISP,
allow simple formulations of complex tree strategies.
The description involves discussion of the abstract data structures and 
their representations.  The objects are finitely branching trees; that is,
we assume that any node in a tree can have any finite
number of branches. We will also assume that the
trees will terminate on all of their branches.
We need a recognizer,
 named %3is_term%1, which will return %et%1 if the tree is the trivial
terminal tree  with no branches. A terminal tree may either be a %3WIN%1 or a 
%3LOSS%1. If it's a win, we know how to achieve our goal; if it's a 
%3LOSS%1, then we  look further. 
That "further" says examine the 
 alternatives  the immediate parent of that
 node; if there aren't any alternatives
then back up to the grandparent.

If a tree has branches they are located by the selector %3branches%1.
We will assume those branches are presented as an ordered sequence,
perhaps ordered by their plausible value. Therefore we will use
the selectors %3first%1 and %3rest%1 to select candidate branches.

.BEGIN GROUP;SELECT 3;TABIT2(20,23);
.boxa
eval_tree[tr] <= [\is_term[tr] → [is_win[tr] → tr; %et%3 → %3LOSS%1];
\%et%3 → eval_branches[branches[tr]]]
.pt18
eval_branches[l] <= [\null[l] → LOSS;
\\eq[LOSS;eval_tree[first[l]]] → eval_branches[rest[l]];
\\%et%3 → first[l]]
.boxb
.END

.fp
The simplicity of the description is pleasing. It encourages us to 
proceed to more complex tree strategies.

Attempts at exhaustive search of  game trees becomes prohibitively
expensive when applied to games like
checkers and chess. However, computers have had reasonable
success at checkers, and are beginning to play passable
chess. A recent article, ⊗↑[Sug#77]↑,  addresses the feasibility of
home  chess machines. Those successes are based on more sophisticated analysis
of game trees. The ideas involved in that analysis are easily expressed
in LISP.

In the following discussions we will make several assumptions.
.nl
%21.%1##Our opponent is as smart as we are. 
This assumption allows us to use  %6our%1 evaluation function
in evaluating the positions of our opponent.
.nl
%22.%1##We 
assume that our opponent is also trying to win. Therefore his move will
reflect his best attempt to  defeat us.
Since we are using the same position-evaluator,
his "maximal harm" is our "minimal good".
We are thus following a "%2max-min%1" strategy 
 wherein we attempt to find the best move
which our opponent cannot turn into    a disaster  for us. 
.boxb

From these ideas we formulate our position evaluation strategy as follows:
.nl
%21.%1##Grow a tree of moves. First our possible moves from a position, then
his counter moves; then our responses, etc. Continue this until the
branch terminates or until a termination condition is
forced.⊗↓We assume we have  methods for 
determining when a move is already present in the tree.←  
.nl
%22.%1##Once the tree is built, we evaluate the terminal nodes.
.nl
%23.%1##The values are propagated back up the tree using the min-max idea.
If the preceding node is ours, we assign that node the maximum of the
branch values; if the preceding node is his we assign the minimum of the
values. We proceed in this fashion, finally returning the value of the
"best path".
.boxb
.fp
We will simplify matters somewhat, returning only the "value" of the
best path.⊗↓We should really return the  best value %6and%1 a
description of the best path.←  First, we develop some subfunctions:

.BEGIN group;select 3;turn off "∞";tabit1(42);
.boxa
maxlist[l;f] <= [null[l] → -∞; %et%3 → max[\f[first[l]];
\maxlist[rest[l];f]]
.boxb
minlist[l;f] <= [null[l] →  ∞; %et%3 →  min[\f[first[l]];
\minlist[rest[l];f]]
.boxb
.END
.fp
The "%3∞%1" denotes a  number, bigger than any other value
our evaluation function %3f%1 can concoct.
The %3f%1 is a
different kind of variable from those we have seen before.
It is used as a LISP function within the bodies of the definition, yet passed
as a variable. It is therefore called a functional variable. We will discuss such
variables in the next chapter,
 but for now the intent should be clear from some examples:

.BEGIN CENTER;SELECT 3;
.boxa
maxlist[(1 3 5 2);add1] = 6 %1and%3  minlist[(1 3 5 2);add1] = 2 
.END
.boxb
.fp
With those preliminaries, we are ready to present the mini-max strategy:

.BEGIN SELECT 3; GROUP;
.tabit1(17);
.boxa
maxpos[p] <= [\is_term[p] → value[p]; 
\%et%3 → maxlist[branches[p]; minpos]]
.boxa
minpos[p] <= [\is_term[p] → value[p]; 
\%et%3 → minlist[branches[p]; maxpos]]
.boxb
.END
.fp
%3maxpos%1 gives the  value of a position for the maximizing player
and %3minpos%1 gives the  value of a position for the minimizing player.
##%3value%1 is the terminal position evaluation function.

What's even more interesting is that there is a simple technique which
will allow us to discover the optimal path, usually without having to
visit all the nodes. The technique, discovered by John McCarthy in 1958,
is called  %7a%2-%7b%2#pruning%1; it is based on the observation that
if  our opponent is assured that he can force us into an unfavorable position
then he won't make a move which would give us a %6better%1 position.
That's obvious; what is %6not%1 obvious is that he can 
often make such decisions
on the basis of only a partial evaluation of the tree.
Consider:
.BEGIN SELECT g;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#";
.TURN ON "∞" FOR "%";
.boxa
             O
             ~
      ⊂αααααα∀ααααα⊃	opponent∞1'∞gs moves
      ~            ~
      N            M
  ⊂αααβααα⊃    ⊂αααβαα ...⊃    our moves
  ~   ~   ~    ~
  7   3   4    ?    ... 
.boxb
.END
.fp
Since we are to evaluate the position at %gN%1, we maximize the  position,
getting %g7%1; that becomes the value of node %gN%1. It is up to our
opponent to evaluate position %gO%1, and he now knows we're going to
get a %g7%1 if he moves to %gN%1. He looks questioningly at "?"; if that
value is greater than %g7%1 then he immediately rejects move %gM%1 without
examining the other possibilities; things can only get worse for him. 
If "?" is less than
%g7%1, then he looks at additional alternatives at %gM%1. Once our
opponent is finished evaluating the position,  then it's our turn
to play the game at the position above %gO%1, only now we will try to maximize
what that stingy individual has left us.
We let %7a%1 be the value which must be exceeded  for a position to be
desirable by the position about to play; and let %7b%1 be  the value which must
%6not%1 be exceeded if the move leading to the position would be made by the
opponent; in the above example %g7%1 is the %7b%1-value when evaluating
%gM%1. With that, we modify the min-max algorithms to include %7a%1-%7b%1
pruning.
.BEGIN group;select 3;turn off "∞";tabit2(26,42);
.boxa
maxlist%4αβ%3[l;f;%7a%3;%7b%3] <= [\null[l] → %7a%3; 
\f[first[l]] %9≥%1 %7b%3 → %7b%3;
\%et%3 → maxlist%4αβ%3[\rest[l];
\\f;
\\max[%7a%3;f[first[l]]];
\\%7b%3]]
.pt2
minlist%4αβ%3[l;f;%7a%3;%7b%3] <= [\null[l] → %7b%3; 
\f[first[l]] %9≤%1 %7a%3 → %7a%3;
\%et%3 → minlist%4αβ%3[\rest[l];
\\f;
\\%7a%3; 
\\min[%7b%3;f[first[l]]]]]
.boxb
.END
.BEGIN group;select 3;turn off "∞";tabit1(25);

maxpos%4αβ%3[p;%7a%3;%7b%3] <= [\is_term[p] → max[%7a%3;min[%7b%3;value[p]]; 
\%et%3 → maxlist%4αβ%3[branches[p]; minpos%41%3;%7a%3;%7b%3]]
.pt2
minpos%41%3[x] <= minpos%4αβ%3[x;%7a%3;%7b%3]
.boxa
minpos%4αβ%3[p;%7a%3;%7b%3] <= [\is_term[p] → max[%7a%3;min[%7b%3;value[p]]; 
\%et%3 → minlist%4αβ%3[branches[p]; maxpos%41%3;%7a%3;%7b%3]]
.pt2
maxpos%41%3[x] <= maxpos%4αβ%3[x;%7a%3;%7b%3]
.boxb
.END
.fp
The process can be initialized with %7a%1 and %7b%1 set to %3-∞%1 and %3∞%1
respectively. Tighter bounds on "acceptablility" can be enforced by
picking different %7a%1's and %7b%1's. The effect will be to shorten the
search time while, perhaps, ignoring some winning moves; %3caveat emptor%1.

This %6not%1 a trivial algorithm. However its  description as a LISP 
program is about as simple and as compact as you will find; anywhere.

.SS(Data Bases,,P220:)
.begin "db"
.FP
One of the more intriguing applications of LISP is in the area of
data base management. 
In this section we introduce the ideas and suggest
how LISP can be applied to the problems.

A data base is a collection of objects
together with a set of functions to pose questions about the
objects in the base, to select objects from the base, and to construct new
entries in the base. 
Expressed differently, a data base is an abstract data structure.
We need to locate information in the base.
We should be able to ask the system for  a  specific object or
we should be able to partially specify our request ("find all
books about LISP" or "find all books about LISP published before 1975").
We should be able to  add entries and delete entries, but we will postpone
these kinds of requests until  later.

The representational details of objects will be suppressed as usual, and
we will concentrate on the abstract properties.
In our first example, the objects in the data base will represent
constants: an object will have a name and a collection of properties and
values. 

.GROUP
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#","α","←";
.TURN ON "∞" FOR "%";
.BOXA
.KRK

     	⊂αααααααπααααα⊃
        ~ prop1 ~ val1~
	εαααααααβαααααλ
        ~ prop2 ~ val2~
             # # #
	εαααααααβαααααλ
        ~ propn ~ valn~
       	%ααααααα∀ααααα$  		  
.BOXB
.END
.LE(6,An object representation)
.PT24
.APART
For example, a  data base dealing with business supplies
might have objects named boxes. Each box has properties like 
size and contents.

Not all objects need to have the same number of properties. For
example in a data base  whose objects are bibliographic references,
books need not have page references, whereas journal articles require them;
journal references don't include a publisher whereas books do.
The programs which manipulate the data base must be structured to
take changeablility into account.

.GROUP;
Here are some examples: the first one was extracted from the side of a
Xerox paper box; the second might be a representation of a bibliographic entry
for this book.
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#","α","←";
.TURN ON "∞" FOR "%";
.BOXA

     	⊂αααααααπαααααααααααα⊃
        ~ NAME  ~  4029258   ~
	εαααααααβααααααααααααλ
        ~ SIZE  ~ 8-1/2 x 11 ~
	εαααααααβααααααααααααλ
        ~ COLOR ~   WHITE    ~
	εαααααααβααααααααααααλ
        ~ AMNT  ~  10 REAMS  ~
       	%ααααααα∀αααααααααααα$  		  
.END
.APART
.BEGIN SELECT b;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#","α","←";
.TURN ON "∞" FOR "%";

     	⊂ααααααααπααααααααααααααααααααα⊃
        ~ AUTHOR ~     ALLEN, JOHN, R. ~
	εααααααααβαααααααααααααααααααααλ
        ~ TITLE  ~ THE ANATOMY OF LISP ~
	εααααααααβαααααααααααααααααααααλ
        ~ TYPE   ~          BOOK       ~
	εααααααααβαααααααααααααααααααααλ
        ~ PUBL   ~     MCGRAW-HILL     ~
	εααααααααβαααααααααααααααααααααλ
        ~ DATE   ~        1977	       ~
       	%αααααααα∀ααααααααααααααααααααα$  		  
.BOXB
.END
Given a data base of objects, we need to be able to manipulate these objects in
meaningful ways. We will not address the problems of designing
input and output, but will concern ourselves solely with the problems
of semantics of data base primitives: how can we use the information in the 
base?


In requesting information from a data base, we typically  specify
part of the request and expect the system to come up with a set of possibilities
which fit our description. For example, the request: "find all books
about LISP", specifies that we are interested only in books, not in journal
articles or course notes; the topic is specified to be LISP, but 
the system is free to select the other components: the author, the title,
the publisher and the date of publication. The objects which are specified
are called %2constants%1, the unspecified components are %2variables%1.
A request is a structure  called a %2pattern%1 and consists of
an ordered collection of constants and variables.
The elements in the data base are also patterns; for this example, they
contain only constants; such constant patterns are also called records.
The process of discovering whether or not a record in the data base
matches the request is called %2pattern matching%1.


We describe a simple pattern matcher named %3match%1. It expects
two arguments. The first argument is a constant pattern called %3pat%1.
The second argument, %3exp%1
represents a request; it may be constant, or it may contain variables.
If it does contain variables, then  the pattern matching process
must establish a match between those variables and components of our
data base object. The value returned by %3match%1 will either 
represent  the associations built up to match the constant pattern to the
expression, or the value returned will  indicate failure if
no match is possible. 

Patterns will be represented as lists  with atoms representing constants,
and variables represented as lower-case greek letters.
We will represent failure by returning the atom %3NO%1. 
In the case that a match is possible, we will  return a list of 
pairs, where each pair is a variable and its matching constant.
.GROUP;
.BEGIN "XX25" GROUP;CENTERIT
.EQ1(22);
For example:%3\match[(A (B C));(A (B %7a%3))] = ((%7a%3 C))
\match[(A B C);(A %7a%3 %7b%3)] = ((%7a%3 B) (%7b%3 C))
\match[(A B C);(A C %7b%3)] = NO
.END
.END "XX25"
.PT18
.APART

.GROUP;
.FP
Pattern matching can become quite complex. For example:
.BEGIN "XX24" GROUP;CENTERIT
.EQ1(12)
\%3match[(A (B C) (D C));(A (B %7a%3) (%7b%3 C))] = ((%7a%3 C) (%7b%3 D))
\%3match[(A (B C) (D C));(A (B %7a%3) (%7a%3 C))] = NO
.END
.PT18
.END "XX24"
.FP
The second example fails since
once we have associated %3C%1 with %7a%1 we must use that association
throughout the rest of the pattern match; and %3(D#C)%1 does not match
%3(%7a%3#C)%1 when %7a%1 denotes %3C%1.⊗↓This assumes 
that the match proceeds in a left-to-right order.← 
.APART
We will write %3match%1 in terms of a subfunction named %3match%9'%1.
This subfunction carries a third argument, %3mlist%1, which represents the
list of 
partial matches. Whenever we locate a variable in the expression, we
examine the current %3mlist%1. If the variable appears, then we must check
its entry against the corresponding part of the pattern. If the variable
does not occur in %3mlist%1, then we associate the variable with 
the appropriate part of the constant pattern.
.<<BEGIN SELECT 3;GROUP;TABIT3(29,42,50);>>
.BEGIN SELECT 3;GROUP;turn on "\";nofill;krk;TABs 29,42,47,50;
.P229:
.PT24
match[pat;exp] <= match%9'%3[pat;exp;( )]
.PT18
match%9'%3[pat;exp;mlist] <= \[equal[mlist;NO] → NO;
\ isconst[exp] → [\sameconst[pat;exp] → mlist; 
\\\%et%3 → NO];
\ isvar[exp] → check[\pat;
\\\\exp;
\\\\lookup[pat;mlist];
\\\\mlist];
\ %et%3 → match%9'%3[\suffix[pat];
\\suffix[exp];
\\match%9'%3[prefix[pat];prefix[exp];mlist]]
.END

.BEGIN SELECT 3;GROUP;TABIT1(30);
.PT18
check[var;exp;val;mlist] <= [\not[val] → concat[mkent[var;exp];mlist];
\ sameconst[exp;val] → mlist;
\ %et%3 → NO]
.END

.BEGIN SELECT 3; GROUP;TABIT1(19);
.PT18
lookup[var;l] <=\[null[l] → %ef%3;
\ samevar[var;name[first[l]]] → val[first[l]];
\ %et%3 → lookup[var;rest[l]]]
.END
.PT24
.FP
To complete our description of %3match%1 we should supply the data structure
manipulating functions: %3isconst%1, %3isvar%1, %3prefix%1, %3suffix%1, 
%3samevar%1, and %3sameconst%1;
and %3mkent%1, %3name%1, and %3val%1. The first five are related, dealing with
the representation of patterns; the final three involve the representation
of the match list. Note that we %6have%1 assumed that %3mlist%1 is a list.
We will restrict the match algorithm to simple matches on tree structure.
We represent %3prefix%1 as %3first%1 and %3suffix%1 and %3rest%1
though much 
more general interpretations are possible.
We leave it to the reader  to supply representations of the missing functions.

Given a basic pattern matcher, we can begin to elaborate on a
data base management system. We need some means of controlling the matcher.
If several entries in the system match the inquiry, then we must decide how to
manage the matches. In simple cases we could  make a list of all the possibilities.
If the number of matches is very large we might want to  return a few
at a time, remembering where we were in the search of the base.
The natural extension of this idea
is to allow a potentially infinite set of elements present in the data base. 
In programming languages we are able to talk about such potentialities by
using a procedure.

Instead of having objects explicitly
stored in the base, we may allow procedures to occur as data base elements.
Such a procedure would generate elements. For example, instead of storing 
the integers as explicit objects, we could store a procedure to generate
the integers. This introduces two problems: how do we store procedures as
data objects;  and, assuming that we have called such a procedure and
it has delivered an explicit object, how do we represent the
notion that the %6next%1 time we call that procedure, we want the
%6next%1 object?  That is, a procedure named %3get_next_integer%1
should return %31%1 the first time it is called, but know to return
%32%1 the next time it is called in the same context.
It must also know to return %31%1 when it is called in a new context.

Other possible extensions involve the operations on the base.
Assume that  the base
contains "all roses are red" and knows that object O%41%1 is
a rose; if we ask the data base for all red objects, we should expect
to see O%41%1 appear as a candidate. That expectation requires
a deductive ability built into the base manipulator. That is, we need not have
explicitly stored the information in the base, but we expect to be able to
deduce facts from information in the base using some relationships
and reasoning ability.

There are at least two ways the "roses are red" problem can be solved.
Notice that "all roses are red" is much like a procedure; given an
object which is a rose, it generates an object which is red. So,
on entering a rose object in the data base, the system could
also explicitly add the fact that the rose was red. This is an example
of an %2input demon%1. A demon is a procedure which is not explicitly called
but is activated by the occurrence of another event.
Whenever an object is added to the base the collection of input demons
is checked. If an applicable demon is found, it is activated; its activation
might activate other demons. 

The activation of a demon is a different kind of procedure call than
previously seen. The activation is done on pattern matching 
rather than by a user-initiated call.
Thus  the calling style is generally known as 
%2⊗→pattern directed invocation↔←%*#(⊗↑[Hew#72]↑,#⊗↑[Bau#72]↑).
The demon procedure is stored in the data base along with a pattern
which determines conditions for its activation. In the case of an input
demon, an input to the base initiates a match of the input demon patterns
against the input. If a match is found, the corresponding procedures
are executed.
The match process can bind  variables to parts of patterns and therefore the
procedure 
typically has access to the match information.

.GROUP;
Let's establish some notation and give an example.
To introduce records to our system we use a unary procedure named %3add_item%1.
The argument to %3add_item%1 is the record we wish to add.

.BEGIN CENTER;
.BOXA
%3add_item[(ROSE O1)]%1
.BOXB
.END

We will use a ternary procedure named %3add_demon%1 to insert demons
in the base. The first argument is the type of demon; so far we  have
discussed demons invoked by adding elements; we will also
have demons which are applied when items are removed, or when items are
accessed. These three types will be named %3ADD%1, %3REMOVE%1, and %3FETCH%1.
The second argument is the pattern which will invoke this demon; and
the third argument is the action to be taken if the pattern matches.
For example:

.BEGIN CENTER;
.BOXA
%3add_demon[ADD;(ROSE %7a%3);add_item[(RED %7a%3))]]%1
.BOXB
.END


.APART
.FP
Demons are also used to monitor the removal of information from the base.

The third use of demons is involved with another possible solution to the
"all roses are red" problem.
Instead of explicitly adding the fact that %3O1%1 is a red object
we might wait until a request for red objects occurs. At that time
we could use the "all roses are red" demon %6backwards%1.
That is, we could look for any roses in the  data base; the assertion
that a "rose" object is also a "red" object allows us to accept
"rose" objects as solutions to our inquiry.
This feature introduces a certain deductive capability to our system.
It also introduces some organizational problems.

We have to   recognize when a procedure is capable
of producing objects of the desired type. We therefore
index these data base procedures by a pattern which tells what
the procedure accomplishes. That pattern is called the procedure's goal
and the invocation of such a procedure is again pattern-directed, but
has an added connotation of being %2goal-oriented%1.

Again, we introduce some notation and an example. Let the request
for a data base item be given by:
.BEGIN CENTER;SELECT 3;
.BOXA
%3fetch[%7a%3]%1, where %7a%1 is a pattern.
.BOXB
.END
.FP
Since a  %3fetch%1 request might discover several possibilities,
some being items  and some being goal-directed procedures, we 
need a way of examining the selected information.

We introduce a  function named %3try_next%1, whose single
argument is the result of a %3fetch%1. Each call on %3try_next%1
either produces a new item or signals that no more items exist
on the fetch list. 

An extension to this basic data base manipulating system has become 
convenient in artificial intelligence research. Let us assume we wish to
derive a plan or scheme for achieving a desired goal. In the 
derivation process we will make hypotheses and then pursue
their implications. A similar  behavior can be simulated if we allow
the creation of multiple data bases. Each base corresponds to a
hypothetical situation or world, and the  %3fetch%1-ing of
an object in a world corresponds to asking whether or not a 
desired state is attainable in that world. 

Instead of requiring that
all transformations occur in one data base, several systems 
(⊗↑[Con#73]↑, ⊗↑[QA4#72]↑) have implemented a layered data base.
In this situation we are able to add, delete and fetch from specified
data bases. We add two operations %3push_base%1 and %3pop_base%1
which allow us to  manipulate whole data bases as objects.

The control structures necessary for handling such data base manipulations 
may be very non-structured; some of the implementation
ideas for such control  will be discussed in {yonss(P222)}.
We will discuss some details of the data structure implementation  
in {yonss(P128)}.
For more information see ⊗↑[McD#75]↑ and ⊗↑[Con#73]↑.

.CENT(Problems)
.PT24
.NL
1.##Recall our discussion of %3match%1 on {yon(P229)}. 
Supply a representation for match lists and supply the eight
data structure functions.
.NL
2.##The %3match%1 routine we developed on {yon(P229)} required that %3pat%1
be a constant pattern. Write a more general pattern matcher named
%3unify%1 which allows either %3pat%1 or %3exp%1 to contain variables.
This more gereral match routine is called a unifier (⊗↑[Rob#65]↑).
.GROUP;
.PT2
For example:
.EQ1(12)
\%3unify[(A (B %7a%3) A); (A (%7b%3 D) %7d%3)] = ((%7a%3  D) (%7b%3 B) (%7d%3 A))%1
%3
\unify[(A (B %7a%3) A); (A (%7b%3 D) %7b%3)] = NO
\unify[(%7a%3 A  %7a%3); (%7b%3 %7b%3 B)] = NO
.END
.<<ABOVE "END" CLOSES EQ1>>
.APART
.end "db"


.SS(Algebra of Polynomials,,P264:)
.begin "alg"
.BEGIN TURN ON "#";
.FP
%1
Assume that we want to perform addition and multiplication
of polynomials and further assume that each polynomial is of the
form %3p%41%*#+#p%42%*#+#...#+#p%4n%1 where each 
term, %3p%4i%1, is a product of variables
and constants.  
The two components of each term are a constant part called the coefficient,
and the variable part.
We shall assume without loss of generality that the 
set of variables which appear in the polynomials are lexicographically
ordered, e.g.#%3x#<#y#<#z%1;  and assume that each variable part 
obeys that ordering; thus we would insist that %3xzy%82%1 be written %3xy%82%3z%1.
We do not assume that the terms are ordered within the polynomial; thus
%3x#+#xy%1 and %3xy#+#x%1 are both acceptable.
We further assume that the variables of
each %3p%4i%1 are distinct and that no %3p%4i%1 has %30%* as its coefficient.
The standard algorithm for the addition of
%9S%8n%4i=1%3p%4i%1 with   %9S%8m%4j=1%3q%4j%1 indicates that
%3q%4j%1 can be combined with a %3p%4i%1 if the variable parts of these terms 
are identical.  In this
case the resulting term has the same variable part  but has a
coefficient equal to the sum of the coefficients of %3p%4i%1
and %3q%4j%1.
We will examine four representations of polynomials, before finally
writing any algorithms. To aid in the discussion we will use
the polynomial %3x%82%* - 2y - z%1 as our canonical example.

.CENT(First representation)
.FP
We could use the representation of the differentiation
example.  
This would result in our example assuming the form:

.BEGIN CENTERIT;SELECT 3;
.BOXA
←(PLUS (TIMES 1 (EXPT X 2)) (PLUS (TIMES -2 Y) (TIMES -1 Z)))
.BOXB
.END
.FP
The above conventions specify an unambiguous representation for our class
of polynomials. Strictly speaking, we did not need to impose
the ordering on the set of variables. 
However, we need to impose some additional constraints before we
have data structures which are well-suited to the class of polynomial
algorithms we wish to represent.

.CENT(Second representation)
.FP
We are really only interested in testing the equality of the variable parts;
we will not be manipulating variable parts in any other way.
So we might simply represent the variable part as a list of pairs;
each pair contains a variable name and the corresponding value of the exponent.
Knowing that polynomials are always sums, and knowing the class
of algorithms we wish to implement, we write
%9S %3p%4i%1 as:

.BEGIN CENTERIT;
.BOXA
←%3( (%1rep of %3p%41%*), (%1rep of %3p%42%*), ...)%1
.BOXB
.END
.FP
This representation would make our example appears as:

.BEGIN CENTERIT;SELECT 3;
.BOXA
←((TIMES 1 ((X . 2)))  (TIMES -2 ((Y . 1)))  (TIMES -1 ((Z . 1))))
.BOXB
.END
.FP
This representation is sufficient and it does have the 
flexibility we need,  but it is still not terribly  satisfying.
  We are ignoring too much of the structure in our class of 
polynomials.

.CENT(Third representation)
.FP
We know that the occurrence of variables is 
ordered in each variable part; we can assume that we know the class of 
variables which
may appear in any polynomial. So instead of writing %3x%82%*y%83%*z%1
as

.BEGIN CENTERIT;
.BOXA
←%3((X . 2) (Y . 3) (Z . 1))%*,
.PT2
.FP
we could write:###%3(2 3 1)%*##assuming %3x, y, z%* are the only variables.
.BOXB
.END
.FP
In a further simplification, notice that the  %3TIMES%* in the
representation is superfluous. We %6always%* multiply the coefficient by
the variable part. So we could simply %3concat%* the coefficient 
onto the front of the variable part representation.

.BEGIN NOFILL;TURN ON "\";TABS 30,45;GROUP;
.BOXA
Let's stop for some examples.
\%2term\representation
\%32xyz\(2 1 1 1)
.PT2
\2x%82%*z\(2 2 0 1)
.PT2
\4z%83%*\(4 0 0 3)
.END
.BOXB
.FP
Thus our canonical polynomial  would now be represented as:

.BEGIN CENTERIT;SELECT 3;
.BOXA
←((1 2 0 0) (-2 0 1 0) (-1 0 0 1))
.BOXB
.END
.FP
This representation is not too bad; the %3first%*-part of any
term is the coefficient; the %3rest%*-part is the variable part.
For example, the test for equality of variable parts is 
now simply a call on %3equal%*.

Let's start thinking about the structure of the main algorithm.

.CENT(Fourth representation)
.FP
The algorithm for the sum must compare terms. Finding similar terms, it will
generate an appropriate new term, otherwise it simply copies the terms.
When we pick a %3p%4i%1 from the first polynomial we would
like to find a corresponding %3q%4j%1 with the minimum amount of
searching.  
This can be accomplished if we can order the terms
in the polynomials. 
A natural ordering can be induced on  the terms  by
ordering  the numerical representation of the exponents.
For sake of argument, assume 
that a maximum of two digits will be needed to express
the exponent of any one variable. 
Thus the exponent of %3x%82%1 will be represented as %302%*, or 
the exponent of %3z%810%1 will be represented as %310%*. Combining this with our
ordered representation of variable parts, we arrive at:
.GROUP
.BEGIN NOFILL;TABS 30,45;TURN ON "\";
.BOXA
\%2term\representation
.SELECT 3;
\43x%82%*y%83%*z%84\%3(43, 020304)
.PT2
\2x%82%*z\%3(2, 020001)
.PT2
\4z%83%*\(4, 000003)
.END
.BOXB
.APART
%1

.GROUP;
.FP
Now we can order on the numeric representation of the variable
part of the term.  One more change of representation, which will
result in a simplification in storage requirements:

.BEGIN CENTERIT;
.BOXA
←represent %3 ax%8A%3y%8B%3z%8C%1 as %3(a . ABC) 
.BOXB
.END
.APART;
.GROUP;

.SELECT 1;
.FP
This gives our final representation:

.BEGIN CENTERIT;SELECT 3;
.BOXA
←((1 . 20000) (-2 . 100) (-1 . 1))
.BOXB
.END
.FP
Note that %320000 > 100 > 1%1.
.APART

Finally we will write the algorithm.  We will assume that
the polynomials are initially ordered and will write the 
algorithm so as to maintain that ordering.
Each term is a dotted pair of elements: the coefficient
and a representation of the variable part.

.P60:
As in the previous differentiation example, we should 
attempt to extract the algorithm
from the representation.
.GROUP
.FP
We shall define:
.BOXA
.BEGIN CENTERIT;
←%3coef[x] <= car[x]%1 and %3 expo[x] <= cdr[x] 
.END
%1
.BOXB
.FP
To test the ordering we will use the LISP predicate:
.BOXA
.BEGIN CENTERIT;
←%3greaterp[x;y] %1gives %et%1 if %3x%1 is greater than %3y%1.
.END
%1
.BOXB
.APART
.FP
In the construction of the `sum'
polynomial we will generate new terms by combining coefficients.
So a constructor named %3mknode%* is needed.
In terms of the latest representation %3mknode%* is defined as:
.BOXA
.BEGIN CENTERIT;
←%3mknode[x;y] <= cons[x;y]%1
.END
.BOXB
.GROUP
.FP
So here's a graphical representation of our example polynomial:
.BOXA
.BEGIN CENTERIT
←%3x%82%* - 2y - z %1
.END
.BOXB
%3
.BEGIN NOFILL;
.BEGIN SELECT g;NOFILL;PREFACE 0 MILLS;GROUP;
.TURN OFF "%","#";
.TURN ON "∞" FOR "%";
.KRK
			    /\ 
			   /  \
			  /    \
			 /      \
			/\       \
		       /  \      /\
		      1  20000  /  \
			       /    \
			      /\     \
			     /  \     \
			   -2   100   /\
				     /  \
				    /   ∞3NIL∞*
				   /\
				  /  \
				 -1   1
.END
.APART
.GROUP
%1
.FP
Here's the algorithm:
%3
.BEGIN NOFILL;TABS 12,25,34,58,62;TURN ON "\";
.KRK
.BOXA
polyadd[p;q] <=
\[nullpoly[p] → q; 
\ nullpoly[q] → p;
\ greaterp[expo[first[p]];expo[first[q]]] → concat[first[p];
\\\\\polyadd[rest[p];q]];
\ lessp[expo[first[p]];expo[first[q]]] → concat[first[q];
\\\\polyadd[p;rest[q]]];
\ zerop[plus[coef[first[p]];coef[first[q]]]] → polyadd[rest[p];rest[q]];
\ %et%* → concat[\mknode[\plus[coef[first[p]];coef[first[q]]];
\\\expo[first[p]]];
\\polyadd[rest[p];rest[q]]]] 
.BOXB
.END

.BEGIN CENTERIT;

%1where:%3←←zerop[x]  <= eq[x;0]
.END
%1
.APART
.FP
.GROUP
Notice that our algorithm is quite abstract.
Now for an explanation and example. The form of %3polyadd%* is: 
%1
.P72:

.BEGIN FILL;
.FP
%3[%2p%41%3 → %2e%41%3; %2p%42%3 → %2e%42%3; 
%2p%43%3 → %2e%43%3; %2p%44%3 → %2e%44%3; 
%2p%45%3 → %2e%45%3; %2p%46%3 → %2e%46%3]
.END
.APART;

.GROUP;
.BEGIN SELECT 1;INDENT 0,10;FILL;
%2p%41%3 → %2e%41%1 and %2p%42%3 → %2e%42%1 check if either polynomial is empty.
.PT2
.FP
%2p%43%3 → %2e%43%1 and %2p%44%3 → %2e%44%1  examine the ordering of
terms so that the resultant polynomial retains the ordering.
.PT2
.FP
%2p%45%1 or %2p%46%1 will not be reached unless the variable parts are equal.
.PT2
.FP
%2p%45%3 → %2e%45%1.  Since the variable parts are equal, we can  combine
terms.  However, we must check for cancellations and not include any 
 terms with zero coefficient in our resultant polynomial.
.PT2
.FP
%2p%46%3 → %2p%46%1.  In the final case we must add a new node to our polynomial.
.END
.APART;
%1
.GROUP
.FP
Here's an informal execution of %3polyadd:

.BEGIN NOFILL;TABS 10;TURN ON "\";
.KRK
.BOXA
.SELECT 3;
polyadd[ x+y+z; x%82%*-2y-z ]
\= concat[x%82%*;polyadd[x+y+z; -2y-z]]
\= concat[x%82%*;concat[x;polyadd[y+z; -2y-z]]]
\= concat[x%82%*;concat[x;concat[node[1+-2;y];polyadd[z;-z]]]]
\= concat[x%82%*;concat[x;concat[-y;polyadd[z; -z]]]]
\= concat[x%82%*;concat[x;concat[-y;polyadd[( );( )]]]]
\= concat[x%82%*;concat[x;concat[-y;( )]]]
.BEGIN CENTERIT;
←= x%82%*+x-y
.BOXB
.END
.END
.APART
.END
.END
.FP
Extensive work has been done on  polynomial manipulating algorithms
for efficient storage  and fast  execution (⊗↑[Got#76]↑).
.CENT(Problem)
.NL
1.##Write an algorithm, %3polymult%1, to perform the multiplication
of two polynomials.
.end "alg"
.SS(Evaluation of Polynomials,,P2:)
.begin "eval"
.BEGIN "D3" TURN ON "←";
.BEGIN "D1";
.FP
Though you are undoubtedly quite tired of looking at polynomials, there is
at least one more operation which is usefully performed on polynomials.
The operation is evaluation.
Given an arbitrary polynomial, and values for any of the variables which it
contains, we would like to compute its value. First we will
assume that  the substitutions of values for variables has already been
carried out. Thus we are dealing with polynomials of the form: %9S%8n%4i=1%3p%4i%1
where %3p%4i%1 is a product of powers of constants. For example:
.BOXA
←%32%83%* + 3*4%82%* + 5%1 
.BOXB
.FP
This could be represented as:
.BOXA
←%3(PLUS (EXPT 2 3) (PLUS (TIMES 3 (EXPT 4 2)) 5))%*
.BOXB
.FP
We have taken this general representation because we have great expectations
of generalizing the resulting algorithm.

We  describe a LISP function, %3value%*, which will take such an
S-expr representation and compute its value. Input to %3value%* will be
numerals or lists beginning with either %3PLUS, TIMES,%* or %3EXPT%*
and followed by two numerals or other expressions of the same form.

.BEGIN TABIT1(13);GROUP;
.BOXA
<constexp>\::= <constant> 
\::= <sum> 
\::= <prod>
\::= <expt>
.PT2
<sum>\::= %3(PLUS%1 <constexp> <constexp> %3)%1
.PT2
<prod>\::= %3(TIMES%1 <constexp> <constexp> %3)%1
.PT2
<expt>\::= %3(EXPT%1 <constexp> <constexp> %3)%1
.PT2
.boxb
.END

The value of a numeral is that numeral; to evaluate the other forms of input
we should perform the operation represented. We must therefore assume
that operations of addition, multiplication, and exponentiation exist.  
Assume they are
named +, *, and ↑, respectively. What then should be the value of a representation
of a sum?
It should be the result of adding the value of the representations of the
two summands or operands. That is, %3value%* is  recursive.
It should now be clear how to write %3value%*:

.BEGIN TABIT1(14);SELECT 3;
.BOXA
value[x] <=\[isconstant[x] → x;
\ issum[x] → +[value[arg%41%*[x]];value[arg%42%*[x]]];
\ isprod[x] → *[value[arg%41%*[x]];value[arg%42%*[x]]];
\ isexpt[x] → ↑[value[arg%41%*[x]];value[arg%42%*[x]]]]
.END
.PT18
.BEGIN  "XX26" GROUP;CENTERIT;SELECT 3;
.EQ1(26)
%1where:%3\isconstant[x] <= numberp[x]
\issum[x] <= eq[first[x];PLUS]
\isprod[x] <= eq[first[x];TIMES]
\isexpt[x] <= eq[first[x];EXPT]
.BOXB
.END
.END "XX26"
Compare the structure of the evaluator with that of the BNF equations.
.<<PROBLEMS ON POLY EVAL >>
.SELECT 1;
.CENT(Problems)
.PT24
.NL
1.##Show how to extend %3 value%* to handle binary and unary minus.
.NL
2.##Write an algorithm  %3instantiate%*  which will take two arguments,
one representing a set of variables and values, the other representing
a polynomial. The algorithm is to return a representation of the
polynomial which would result from substituting the values for the variables.
.NL
3.##We would like to represent  expressions like 2+3+4 as
%3(PLUS#2#3#4)%* rather than %3(PLUS#(PLUS#2#3)#4)%* or %3(PLUS#2#(PLUS#3#4))%*;
or represent 2*3*4+5+6 as %3(PLUS#(TIMES#2#3#4)#5#6)%*.
Write a new version of %3value%* which can evaluate  such n-ary representations
of + and *.

.CENT(More on polynomial evaluation)
.FP
Though it should be clear that the current %3value%* function does perform
the appropriate calculation, it should be equally clear that the class of
expressions which %3value%* handles is not particularly powerful.
We might wish to evaluate  requests like:

.BEGIN tabit1(15);
.P122:
.BOXA
%2A%*\"What is the value of %3x*y + 2*z%* when %3x=4, y=2,%1 and %3z=1%*?"
.END
.BOXB
.P266:
.FP
Now the function %3instantiate%*, requested in problem 2  above, offers
one solution: make a new copy of the representation of %3x*y#+#2*z%*
with the variables replaced by their 
values.⊗↓We have seen this substitution and simplification process before in
discussing %3equal%1 on {yon(P1)}.
It is a  useful model for computation, but does not reflect
current implementation practice. However, see ⊗↑[Ber#75]↑.←  This would result
in a representation of %34*2#+2*1%*, and this new expression is suitable
fare for %3value%*. Computationally, this is a terrible solution.
%3instantiate%* will go through the structure of the expression looking
for instances of variables, and when located, will replace them with
the  appropriate values. %3value%* then goes through the structure of
the resulting expression performing the evaluation. We desire
 a function, %3value%9'%1, which combines the two processes: 
the basic structure of %3value%9'%1 is that of mild-mannered %3value%*,
but when a variable, say %3x%*, is recognized inside %3value%9'%1 then %3value%9'%1
would look at a table like that expected by %3instantiate%*, find %3x%*
and return the value associated with the entry for %3x%*.

.BEGIN TURN OFF "{","}";TURN ON "#";
Let's formalize our intuitions about %3value%9'%1. 
It will be a function of two arguments. The first will be a
representation of a polynomial; the second will be a representation of
the table of variables and values. 
You may have noticed that the original version of %3value%*
%6does%1 handle expressions which are not actually constant
polynomials; %3(2#+#3)*4%* for example. Since we will wish to
apply our evaluation functions to more general classes of expressions
we will continue, indeed encourage, this generality.
Regardless of the class of expressions we wish to examine, it is
the structure of the table which should be the first order of business.
An appropriate table, %3tbl%*, will be a set of ordered pairs  
%3<name%4i%*,#val%4i%*>%1;
thus for the above example the table %3{<x,#4>,#<y,#2>,#<z,#1>}%1 would suffice.
Following our dictum of abstraction and representation-independent programming,
we will not worry about the representational problems of such tables. We will
simply assume that "tables" are instances of an abstract data structure  
called %d<table>%*, and we will only
concern ourselves for the moment with the kinds of operations we need
to perform. We will need two selector functions: %3name%*, to select
the variable-component of a table entry; and  %3val%*, to select the
value-component. A complete discussion of such a data structure would
entail discussion of constructors and recognizers, and perhaps other
functions, but for the current %3value%9'%1, these two functions will suffice.

%3value%9'%1 will need a table-function, %3locate%*, to locate an appropriate
variable-value entry. The binary function
%3locate%* will take an  argument, %3x%*, 
representing a variable;
and an  argument, %3tbl%*, representing a table. 
%3locate%* will match %3x%* against the
%3name%*-part of each element in %3tbl%*; 
if a match is found then the corresponding
%3val%*-part is returned. If no match is found then %3locate%* is undefined.

So far, little structure has been imposed on elements of %d<table>%*;
tables are either empty or not; but if a table is non-empty then each
element is a pair with recognizable components of %3name%1 and %3val%1.
However, the specification of  algorithms to examine
elements of %d<table>%* imposes more structure on our tables.
If we were dealing with 
mathematical functions 
rather than algorithms then a side condition to the effect
that a table had no pairs with duplicate first elements would be sufficient
(and required).
However, we are dealing with algorithms and therefore  must describe a method for
locating elements. 

Recursion is the only method we have for  specifying
%3locate%*, and recursion operates by decomposing a structure. Sets are
notorious for their lack of structure; there is no order to the elements of a
set. But if we are to write a LISP algorithm for %3locate%*, that algorithm will
have to be recursive on the "structure" of %3tbl%*,
and so we impose an ordering on the elements of that
table. That is, we will represent tables as %6sequences%*. We know
how to represent sequences in LISP: we use lists.
.END
.BEGIN GROUP;TURN ON "{","}";
With this introduction, here's %3locate%*:⊗↓The  interpretation
of %3tbl%* as a function implies that %3locate%* represents function application;
i.e., %3locate[x;tbl]#%1is%*#tbl(x)%*.This is a very acceptable view
of table lookup.← 
.BEGIN TABIT1(18);SELECT 3;GROUP;
.P123:
.BOXA
locate[x;tbl] <=\[eq[name[first[tbl]];x] → val[first[tbl]];
\ %et%* → locate[x;rest[tbl]] ]
.BOXB
.END
.END
.FP
The effect of %3locate%1 is to find the %6first%1 element of %3tbl%1 which
has a %3name%1-component which matches %3x%1.  Having found that
match, the corresponding %3val%1-part is returned. If there were other
matches further along in the sequence %3locate%1 would not see them.
Other representations of tables are certainly possible. This representation
will be useful in later applications.

.BEGIN TABIT2(19,35);GROUP;
And here's the new more powerful %3value%9'%1:
.BOXA
.SELECT 3;
value%9'%*[x;tbl] <=\[isconstant[x] → x;
\ isvar[x] → locate[x;tbl];
\ issum[x] → +[\value%9'%*[arg%41%*[x];tbl];
\\value%9'%*[arg%42%*[x];tbl]];
\ isprod[x] → *[\value%9'%*[arg%41%*[x];tbl];
\\value%9'%*[arg%42%*[x];tbl]];
\ isexpt[x] → ↑[\value%9'%*[arg%41%*[x];tbl];
\\value%9'%*[arg%42%*[x];tbl]] ]
.BOXB
.END
.FP
Notice that %3tbl%* is carried through  as an explicit argument to 
%3value%9'%1 even though it is only accessed when a variable is recognized.
Notice too that much of the structure of %3value%9'%1 is quite repetitious;
the lines which handle sums, products, and exponentiation are identical
except for the function which finally gets applied to the evaluated arguments.
That is, the basic structure of %3value%9'%1 is potentially of broader application
than just the simple class of polynomials.
In keeping with our search for generality, let's pursue %3value%9'%1 a little
further.

What %3value%9'%1 says is:
.PT24
.NL
%21.%*##The value of a constant is that constant.
.NL
%22.%*##The value of a variable is the current value associated with 
that variable in the table.
.NL
%23.%*##The value of a function call is the result of
applying the function to the evaluated arguments. It just turns out
that the only functions %3value%9'%1 knows about are binary sums, products,
and exponentiation.
.PT24
.GROUP
.fp
Let's clean up %3value%9'%1 a bit.
.BEGIN TABIT2(18,44);SELECT 3;GROUP;
.BOXA
value%9'%*[x;tbl] <=\[isconstant[x] → x;
\ isvar[x] → locate[x;tbl];
\ isfun_args[x] → apply[\fun[x];
\\eval_args[args[x];tbl]];
\ %et%3 → %9B%3]
.BOXB
.END
.APART
.FP
The changes are in the third branch of the conditional. We have a new
recognizer, %3isfun_args%* to recognize
function application. We have two new selector functions; %3fun%*
selects the representation of the function --#sum, product, or power
in the simple case; %3args%* selects the arguments or parameters to the
function --#in this case all functions are binary. We have two
new functions to define: %3eval_args%*, which is supposed to evaluate
the arguments finding  values for any of the variables; 
and %3apply%*, which is used to perform the desired operation on the evaluated
arguments.

.BEGIN TURN OFF "}","{"; TURN ON "#";
We are still trying to remain as representation-free as possible: thus
the generalization of the algorithm %3value%9'%1, and thus the care
in picking representations for the data structures.
We need to make another data structure decision now; when writing the 
function %3eval_args%*, we will be giving a recursive algorithm.
This algorithm will be recursive on the structure of the first argument,
which is a representation of the arguments to the function. In contrast
to our position when writing the function %3locate%*, there %6is%* a
natural structure on the arguments to a function: they form a 
sequence. That is %3f[1;2;3]%* is typically not the same as %3f[3;2;1]%*
or %3f%1 applied to any other permutation of {1,#2,#3}. 
Thus writing %3eval_args%* as a function,
recursive on the sequence-structure of its first argument, is quite
natural. Here is %3eval_args%*:
.END
.BEGIN TABIT2(25,38);SELECT 3;GROUP;
.BOXA
eval_args[args;tbl] <=\[null[args] → ();
\ %et%* → concat[\value%9'%*[first[args];tbl];
\\eval_args[rest[args];tbl]] ]
.BOXB
.END
.FP
Notice that we have written %3eval_args%* without any bias toward binary
functions; it will evaluate a sequence of arbitrary length, returning a sequence
representing the evaluated arguments.

.GROUP;
There should be no real surprises in %3apply%*; it gets the representation
of the function name and the sequence of evaluated arguments and
does its job:

.BEGIN TABIT2(25,42);SELECT 3;GROUP;
.BOXA
apply[fn; evargs] <=\[issum[fn] → +[\arg%41%*[evargs];
\\arg%42%*[evargs]];
\ isprod[fn] → *[\arg%41%*[evargs];
\\arg%42%*[evargs]];
\ isexpt[fn] → ↑[\arg%41%*[evargs];
\\arg%42%*[evargs]] ]
.BOXB
.END
.APART
.FP
If we should desire to recognize more functions then we need only
modify %3apply%*. That would be a satisfactory short-term solution, but  we
 would like a more general
function-definition facility. Such a  feature would allow new functions to
be defined during a computation; then if an application of that function
were needed, the %3value%*-function would find that definition and
apply %6it%* in a manner analogous to the way the pre-defined functions are
applied. 
How far away are we from this more desirable  super-%3value%*?
Well %3value%9'%1 is already well-endowed with a mechanism for locating
values; perhaps we can exploit this judiciously placed code.
In what context would we be interested in locating function definitions?
Here's an example:

.BEGIN tabit1(15);
.P124:
.BOXA
%2B%*\"What is the value of %3f[4;2;1]%* when %3f[x;y;z] <= x*y + 2*z%*?"
.BOXB
.END
.FP
If we have a means of recovering the definition of %3f%*,
then we can reduce the problem to %2A%* of {yon(P122)}.
We will utilize the table-mechanism, and therefore will use %3locate%*
to retrieve the definition of the function %3f%*.
In our prior applications of %3locate%* we would find a constant
as the associated value. Now, given the name %3f%*, we would expect
to find the definition of the function.
The question then, is how do we represent the definition of %3f%*?
Certainly  the body of the function, %3x*y#+#2*z%*, is one of the
necessary ingredients, but is that all? Given the expression %3x*y#+#2*z%*
can we successfully compute %3f[4;2;1]%*?
Not yet; we need to know the correspondence between the values %31,#2,#4%*
and the variables, %3x, y, z%*. That information is present in our
notation %3f[x;y;z]#<=#...%*, and is a crucial part of the definition of %3f%*.
That is, the %6order%* of the variables appearing after the function name
is an integral part of the definition:
%3f[y;z;x]#<=#x*y#+2*z%* defines a different function.

Since we are now talking about %6representations%* of functions, we
are entering the realm of abstract data structures again. We have a
reasonable understanding now of the essential components of such a representation.
.group
For our purposes, a function has three parts:

.BEGIN INDENT 10,10;
.PT24;NL
%21.%*##A name; %3f%* in the current example.
.NL
%22.%*##A formal parameter list; %3[x;y;z]%* here.
.NL
%23.%*##A body; %3x*y + 2*z%* in the example.
.END
.apart
.PT24
.FP
We do not need a complete study of representations for functions yet. For
our current discussions we can assume a representation exists, and that
we are supplied with three selectors to retrieve the components mentioned
above.
.PT24
.NL
%21.%*##%3name%* selects the name component from the representation. We have
actually seen %3name%* before in the definition %3locate%* on {yon(P123)}.
.NL
%22.%*##%3varlist%* selects the list of variables from the representation.
We have already seen that the natural way to think about this component
is as a sequence. Thus the name  %3varlist%*.
.NL
%23.%*##%3body%* selects the expression which is the content of the definition.
.PT24
.FP
Given a function represented in the table according to these conventions, how
do we use the information to effect the evaluation of something like 
%3f[4;2;1]%*?
First %3value%9'%1 will see the representation of %3f[4;2;1]%*;
it  should recognize this as an instance of function-application at the following
line of %3value%9'%1:
.BOXA
.BEGIN CENTERIT; SELECT 3;
←isfun_args[x] → apply[fun[x];eval_args[args[x];tbl]]
.BOXB
.END
.FP
This should cause an  evaluation of the arguments and then
pass on the work to %3apply%*.

Clever %3apply%* should soon realize that %3f%* is not the name of a 
known function. It should then extract the definition of %3f%* from the
table; associate (or bind)  the evaluated arguments (%34,#2,#1%*) with the variables 
of the parameter list (%3x,#y,#z%*), making a new table with name-value pairs
(%3<x,#4>,#<y,#2>,#<z,#1>%1).
Now we are back to the setting of problem %2A%* of {yon(P122)}.
We should ask %3value%9'%1 to evaluate the %3body%*-component
of the function using the new %3tbl%*.
This works fine for %3x%1, %3y%1, and %3z%1; within the evaluation of the body
of %3f%1 we will find the right bindings for these variables. But we might 
also need some information from the original %3tbl%1. The evaluation of the
body of %3f%1 might entail the application of some function definition
present in %3tbl%1. For example, the representation of 

.BEGIN CENTERIT;
.P265:
.BOXA
←"what is %3g[2]%1 where %3g[x] <= x+s[x];%1 and %3s[x] <= x*x%1#?"
.END
.BOXB
.FP
Within the body of %3g%1 we need the definition of %3s%1. Therefore,
instead of building a new table we will add the new bindings to the front of the
old table. Since %3locate%1 begins its search from the front of the table
we will be assured of finding the new bindings; since the old table is still
accessible we are assured of finding any necessary previous bindings.

We should be able to create a new %3value%9''%1 now.
Looking at the finer detail of %3value%9'%1 and %3apply%*,
we can see a few other modifications need to be made.
%3apply%9'%1 will        locate   the function
definition and thus %3tbl%* should be included as a third argument to 
%3apply%9'%1. That is, inside %3apply%9'%1 we will have:

.BEGIN CENTERIT;
.BOXA
←%3isfun[fn] → apply%9'%3[locate[fn;tbl];evargs;tbl]%1;
.END
.BOXB
.FP
After %3locate%1 has done its work,
this line (above) will invoke %3apply%9'%1 with a function definition as first
argument. We should   prepare  %3apply%9'%1 for such an eventuality with the
following addition:
.BEGIN CENTERIT; SELECT 3;
.BOXA
←isdef[fn] → value%9''%*[body[fn];newtbl[varlist[fn];evargs;tbl]];
.END
.BOXB
.FP
What does this incredible line say? It says 
.boxa
.BEGIN INDENT 7,7,7;
"Evaluate the body of the function using a new table manufactured from
the old table by adding the pairings of the elements of the formal parameter
list with the evaluated arguments."
.END
.boxb
.FP
It also says we should   write %3newtbl%*. This LISP function will make
a new table by adding new name-value pairs to an existing table.
So we'd better name a constructor
to generate a new name-value pair:
.DEF
%3mkent%* is the constructor to make new entries. It will take two arguments:
the first will be the name, the second will be the value.
.boxb
Since we have assumed that the structure of tables, variable-lists, and
calling sequences to functions are %6all%* sequences, we will
write %3newtbl%* assuming this representation.

.BEGIN TABIT3(26,38,46);GROUP;SELECT 3;
.BOXA
newtbl[vars;vals;tbl] <=\[null[vars] → tbl;
\ %et%* → concat[\mkent[first[vars];first[vals]];
\\newtbl[\rest[vars];
\\\rest[vals];
\\\tbl]] ]
.END
.BOXB
.GROUP;
.FP
And finally here's the new %3value%9''%*-apply%9'%1 pair:
.P125:

.BEGIN TABIT2(20,47);SELECT 3;GROUP;
.BOXA
value%9''%*[x;tbl] <=\[isconstant[x] → x;
\ isvar[x] → locate[x;tbl];
\ isfun_args[x] → apply%9'%3[\fun[x];
\\eval_args[args[x];tbl];
\\tbl] ]
.BOXB
.END
.APART;
.BEGIN TABIT3(27,49,57);SELECT 3;GROUP;

apply%9'%3[fn;evargs;tbl] <=\[issum[fn] → +[arg%41%*[evargs];arg%42%*[evargs]];
\ isprod[fn] → *[arg%41%*[evargs];arg%42%*[evargs]];
\ isexpt[fn] → ↑[arg%41%*[evargs];arg%42%*[evargs]];
\ isfun[fn] → apply%9'%*[locate[fn;tbl];evargs;tbl];
\ isdef[fn] → value%9''%*[\body[fn];
\\newtbl[\varlist[fn];
\\\evargs;tbl]] ]
.END
.BEGIN TABIT2(25,37);SELECT 3;GROUP;

eval_args[args;tbl] <= \[null[args] → ( );
\ %et%* → concat[\value%9''%*[first[args];tbl]; 
\\eval_args[rest[args];tbl]] ]
.END
.BOXB
.END "D1";
Let's go through a complete evaluation of %2B%* of {yon(P124)}.
As before, we will use %eR%* as a mapping from expressions to representations.
Thus we want to pursue: 
.BEGIN "D2" TURN ON "←";TURN OFF "{","}";
.BOXA
←%3value%9''%*[%eR%f(%3 f[4;2;1] %f)%*; %eR%f(%3{ <f, [[x;y;z] x*y + 2*z]> }%f)%3]%1.
.BOXB
.FP
Let us denote the initial symbol table, 
%eR%f(%3{#<f,#[[x;y;z]#x*y#+#2*z]>#}%f)%1 as %3init%1. This will simplify many 
of the expressions.
Notice that
our representation of %3f%* in %3init%1 has associated the variable list %3[x;y;z]%1
with the body of the function. Thus %3locate%1, operating on this table with the
name %3f%1, will return a representation of %3[[x;y;z]#x*y#+#2*z]%1.

.GROUP;
The recognizer
%3isfun_args%* should be satisfied and thus the computation should reduce to:
.BEGIN TABIT2(10,19);
.BOXA
\%3apply%9'%3[\fun[%eR%f(%3 f[4;2;1] %f)%3];
\\eval_args[args[%eR%f(%3 f[4;2;1] %f)%3];init];
\\init]%1
.BOXB
.END
 or:←%3apply%9'%3[
%eR%f(%3 f %f)%3
;eval_args[
%eR%f(%3 [4;2;1] %f)%3;
init];
init
]
.BOXB
.APART;
.GROUP;
.FP
%3eval_args%1  will build a sequence of the evaluated arguments: %3(4,#2,#1)%1,
resulting in:

←%3apply%9'%3[
%eR%f(%3 f %f)%3
;(4, 2, 1)
;
init
]
.APART;
.GROUP;
.BOXB
.FP
%3apply%9'%1 should decide that %3f%* satisfies %3isfun%* giving:
.BOXA
←%3apply%9'%*[
locate[
%eR%f(%3 f %f)%3
;
init
];
(4, 2, 1)
;
init
]%1
.BOXB
.APART;
.GROUP;

.FP
%3locate%* will  retrieve the definition, and

←%3apply%9'%*[
%eR%f(%3  [[x;y;z] x*y + 2*z] %f)%3
;
(4, 2, 1)
;
init
]%1 
.FP
should be the result.
.APART;
.GROUP;

Next, %3apply%9'%1 should realize that 
%eR%f(%3  [[x;y;z] x*y + 2*z] %f)%1 satisfies 
%3isdef%1  and thus:

.BEGIN TABIT3(10,18,26)
.BOXA	
\%3value%9''%*[\body[%eR%f(%3  [[x;y;z] x*y + 2*z] %f)%3];
\\newtbl[\varlist[%eR%f(%3  [[x;y;z] x*y + 2*z] %f)%3];
\\\(4,2,1);
\\\init]]%1
.END
.BOXB
.FP
or:←%3value%9''%*[
%eR%f(%3  [x*y + 2*z] %f)%3
;newtbl[
%eR%f(%3  [x;y;z]  %f)%3
;(4,2,1);init]]%1
.pt2
.FP
after %3body%* and %3varlist%* are finished.
.APART;
.GROUP;
.FP
.boxb
%eR%f(%3#[x;y;z]#%f)%1 is 
%3(%eR%f(%3#x#%f)%3,#%eR%f(%3#y#%f)%3,#%eR%f(%3#z#%f)%3)%1, 
and therefore the computation of
%3newtbl%*  will build a new table with entries for %3x,#y,#%1#and#%3z%1 on
the front:
.BOXA
←%eR%f(%3{ <x, 4>, <y, 2>, <z, 1>, <f, [[x;y;z] x*y + 2*z]> }%f)%1.
.BOXB
.APART;
.GROUP;
.FP
Thus we call %3value%9''%1 with:
.begin tabit2(5,13);
.BOXA
\%3value%9''%*[\%eR%f(%3  [x*y + 2*z] %f)%3;
\\%eR%f(%3{ <x, 4>, <y, 2>, <z, 1>, <f, [[x;y;z] x*y + 2*z]> }%f)%3]%1
.BOXB
.end
.APART;
.END "D2";
.FP
Now we're  back at problem %2A%* of {yon(P122)}.
.CENT(Time to take stock)
.BEGIN "STOCK"
.FP
We have written a reasonably sophisticated algorithm here;
we should 
examine the results quite carefully.
Notice that we have written the algorithm with almost no
concern for representation. We %6assume%* that representations
are available for such varied things as arithmetic expressions,
tables, calls on functions, and even function definitions. Very
seldom did we commit ourselves to anything close to a concrete
representation, and then only with great reluctance. It was
with some sadness that we imposed a sequencing on elements of
tables.  
Variable lists and calling sequences were not as traumatic;
we claimed their natural structure was a sequence. As always,
if we wish to run these programs on a machine we must supply some
representations, but even then the representations will only
interface with our algorithms at the constructors, selectors and recognizers.

We have made some more serious representational decisions in
the structure of the algorithm.  We have encoded a version
of the %2CBV%*-scheme of {yon(P121)}. We have seen what kinds of
difficulties   that    can cause. We will spend a 
large amount of time in {yonsec(P113)} discussing the problems
of evaluation.⊗↓A second decision was implied in our handling of function
definitions; namely we bound the function name to a data structure representing
the formal  parameter list and the function body. This representation 
gives the expected result in most cases, but involves one of the
more problematic areas of programming languages: how do you
find the bindings of variables which do not appear in the current variable
list? For example, function names belong in this category. 
Such variables are called
non-local variables. The scheme proposed in this section finds the
binding which is current when the function was applied. 
This corresponds to the "latest active" binding made for the variable
in question.
Some programming
languages, in particular LISP, follow this strategy; 
some other languages follow Algol#60 and 
use the binding which was current
when the function was defined, and some languages allow both. 
The next two chapters begin a study of binding strategies.← 

.P186:
Finally, our decisions on the data structures and the algorithms were not
made independently. For example, there is strong interaction between 
our representation
of tables and the algorithms, %3locate%1 and %3newtbl%1 which  manipulate
those tables. We should ask how much of this interaction is inherent 
and how much is gratuitous. For example, we have remarked that our representation
can contain pairs with duplicate first elements. It is the responsibility of %3locate%1
to see that we find the expected pair. If we wrote %3locate%1 to search from right
to left, we could get the wrong pair. 
We %6could%1 write %3newtbl%1 to be more selective; it could manufacture
a table without such duplications:

.BEGIN nofill; turn on "\";TABs 27,39,51,59,69 ;GROUP;SELECT 3;
.KRK
.BOXA
newtbl[vars;vals;tbl] <= \[null[tbl] → \[null[vars] → ();
\\ %et%3 → concat[\mkent[first[vars];first[vals]];
\\\newtbl[\rest[vars];
\\\\rest[vals];
\\\\( )]]];
\ member[name[first[tbl]];vars] → newtbl[\vars;
\\\\\vals;
\\\\\rest[tbl]];
\ %et%* → concat[first[tbl];
\\newtbl[vars;vals;rest[tbl]]] ]
.END
.BOXB
.FP
This version of %3newtbl%1 requires much more computation than the alternative.
Its advantage is that the "set"-ness of symbol tables is  maintained. 
A disadvantage is that the rebinding process implies a rebuilding of the
table.
The "set" property is one which we need not depend on for our algorithms; in fact,
we will frequently expect that a table is represented as a sequence with
the previous values  of variables  found further along in the sequence.


The main point of this example however is to impress on you
the importance of writing at a sufficiently high level
of abstraction. We have produced a non-trivial algorithm
which is clear and concise. If it were desirable to 
have this algorithm running on a machine we could code it and
its associated data structure representations in a very short time.
In a very short time %6we%* will be able to run this algorithm
on a LISP machine.


.CENT(Problem)
.NL
%21.%1##On {yon(P266)} we mentioned the possibility of writing the new %3value%1
as a combination of old %3value%1 and %3instantiate%1. We rejected
that scheme. On {yon(P265)}  we had to save an old table since we might
need some previously defined functions. We might not have had this difficulty
if we had substituted directly. Write a substitution-type %3value%1 and
use it to evaluate the %3g[2]%1 example.
.END "STOCK"
.END "D3"
.END "eval"
.<<AND THE GREAT MOTHERS>>
.REQUIRE "PROB6.PUB"SOURCE_FILE;
.SS(Another Respite)
.fp
We have again reached a point where a certain amount of reflection would be
beneficial.
Though this is not a programming manual we would be remiss if we did not
 analyze the programming style which we have been advocating.
.pt24
.NL
%21.%1##Write the algorithm in an abstract setting; do not muddle the abstract
algorithm with the chosen representation.  If you follow this dictum your
LISP programs will never use %3car, cdr, cons%1, and %3atom%*, and rarely use
%3eq%1.
All instances of these LISP primitives will be relegated to small subfunctions
which manipulate representations. 
.NL
%22.%1##When writing the abstract program, do not be afraid to  cast off
difficult parts of the implementation to subfunctions. Remember that if
you have trouble keeping the details in mind when %6writing%* the program,
then the confusion involved in %6reading%* the program at some later time
will be overwhelming. Once you have convinced yourself of the
correctness of the current composition, then worry about the construction
of the subfunctions. Seldom does the process of composing a program flow
so gently from top-level to specific representation. 
Only the toy programs are easy; the construction of the practical
program will be confusing, and will require much rethinking.
But bring as much structure as you can to the process.
.NL
%23.%1##From the other side of the question, don't be afraid to look at
specific implementations, or specific data-structure representations before
you begin to write. There is something quite comforting about a "real"
data structure. Essentially data structures are static objects,⊗↓At 
least within the program presently being constructed.←  while
programs are dynamic objects. A close look at a possible representation
may get you a starting point and as you write the program a distinction will
emerge between a dependence
on the specific representation and the use of
properties of an abstract data structure.
.PT24
Perhaps the more practical reader is overcome by the inefficiencies inherent
in these proposals. Two answers: first, "inefficiency" is a very ethereal concept.
Like "structured programming", it is difficult to define but recognizable
when it occurs.
Hardware development has enabled us to efficiently execute many operations
which were  quite inefficient on earlier machines.
But even at a more topical level, much of what seems inefficient can now be
straightened out by a compiler (see {yonsec(P107)}). 
Frequently, compilers can do very clever optimizations to generate efficient code.
It is better to leave the cleverness to the compiler, and the clarity to the 
programmer.

The current problems in programming are not those of efficiency; they are
problems of %6correctness%*. 
That is, we have a better grasp of techniques for improving efficiency of programs
than we do of techniques for guiding the construction of programs which
work.
How do you write a program which works?
Until practical  tools are developed for proving correctness it is up
to the programmer to certify his programs. Any methodology which  can
aid the programmer will be most welcome.
Clearly, the closer you can write the program to your intuition, the
less chance there is for error. This was one of the reasons for developing
high-level languages. The original motivation for
such languages was a convenient notation for expressing numerical problems.
With data structures, we are able to formalize a broader range of domains, 
expressing our ideas as data structure manipulations rather
than as numerical relationships.

There are at least two 
kinds of errors which are prevalent in data structure programming:
 errors of omission#--#misunderstanding of the basic algorithm; and
errors of commission#--#errors due to misapplied cleverness in attempting
to be efficient.

The occurrences of errors of omission can be minimized
by  presenting the user with
programming constructs which are close to the informal algorithm.
Such constructs include control structures, data structures,
and  representations for operations.

Errors of commission comprise
the great majority of the present day headaches. It is here that programming
%6style%* can be  beneficial: keep the representation of the data structures 
away from the description of the
algorithm; write concise abstract programs, passing off responsibilities to
subfunctions. Whenever a definition of "structured programming" is arrived at,
this advice on programming style will no doubt be included.

The realization that programs %6will%1 have errors or require modification
raises some difficulties for highly structured languages. A realistic debugging
system must allow program modification and data structure modification; if
the language system imposes rigid restrictions on such activities
the programmer's productivity will suffer. Most language systems
have been designed for the %6execution%1 of programs. LISP systems
put a higher premium on %6debugging%1, perhaps because of the
nature of Artificial Intelligence research: the original motivation
for LISP.  LISP programming systems have a high degree of
interactiveness; the result is an effective programming tool.
It is a tool with sharp edges; one can either build mediocre tools which
can't hurt anyone, or can build a sharp tool and expect that
it be applied by knowledgeable users. 
LISP programmers belong in the second classification. Our discussions of LISP
programming style should develop some of the requisite knowledge.

Before closing this discussion of  LISP programming style, we
can't help but note that in the preceding section, %2The Great Progenitors%* have
completely ignored our good advice. This would be a good time for the
interested reader to abstract the %3tgmoaf%* algorithm from the
particular data representation. This detective work will be most
rewarding.

.CENT(Problems)
.NL
1. Write an abstract version of %3tgmoaf%*.
.<<PROVING PROPERTIES>>
.SS(Proving Properties of Programs,,P15:)
.BEGIN TURN ON "←","#";
.FP
People are becoming increasingly aware of the importance of giving 
convincing
arguments for such concepts as the correctness or equivalence of programs. These are
both very difficult enterprises.⊗↓Question of "correctness"  reduce
 to "equivalence" notions in a broad sense,
relating perhaps a declarative specification to a procedural specification.←
We will  sketch a proof
of a simple property of two programs and leave others as problems for the 
interested reader.
How do you go about proving properties of programs?
In {yonss(P120)} we noted certain benefits of defining sets
using inductive definitions.   There was a natural way of thinking about
the construction of an algorithm over that set. We have exploited that 
observation in our  study of LISP programming. We need to recall
the observation that inductive style proofs (see %2PRF%* on {yon(P119)}) 
are valid forms of reasoning
over such domains. Since we in fact defined our data structure domains in
an inductive manner, it seems natural to look for inductive arguments
when proving properties of programs. This is indeed what we do; we perform
induction on the structure of the elements in the data domain.


.GROUP;
For example, given
 the definition of %3append%* given on {yon(P22)} and the definition
of %3reverse%* given on {yon(P23)}, 

.BEGIN SELECT 3;TABIT1(17);GROUP;
.BOXA
append[x;y] <= [null[x] → y; %et%* → concat[first[x];append[rest[x];y]]]
.PT18
reverse[x] <=\[null[x] → ( );
\ %et%* → append[reverse[rest[x]];concat[first[x];( )]]] 
.END
.BOXB
.FP
we wish to show that:
.BOXA
←%3append[reverse[y];reverse[x]] = reverse[append[x;y]]%* 
.BOXB
.FP
for any lists, %3x%*, and %3y%*. The induction will be on the structure of %3x%*.
.APART
.PT24
.BEGIN TABIT3(5,10,15);
.GROUP
\%2Basis%*: %3x%* is %3( )%*.
\We must thus show: %3append[reverse[y];( )] = reverse[append[( );y]]%*
\But: %3reverse[append[( );y]] = reverse[y]%*  by the def. of %3append%* 
\We now establish the stronger result:  %3append[z;( )] = z%* ⊗↓In the following proof
several intermediate steps have been omitted.←
\\%2Basis:%* %3z%* is %3( )%*.
\\Show %3append[( );( )] = ( )%*. Easy.

\\%2Induction step:%* Assume the lemma for lists, %3z%*, of length n;
\\Prove: %3append[concat[x;z];( )] = concat[x;z]%* 
\\Since %3concat[x;z]%* is not %3( )%*, then applying the definition of %3append%*
\\says we must prove: %3concat[x;append[z;( )]] = concat[x;z]%* 
\\But our induction hypothesis is applicable since %3z%1 is shorter than 
\\%3concat[x;z]%1.
\\Our result follows.
\So the Basis for our main result is established.
.APART
.GROUP
.pt18
\%2Induction step:%* Assume the result for lists, %3z%*, of length n;
\Prove:
\(1)  %3append[reverse[y];reverse[concat[x;z]]] 
\\#########= reverse[append[concat[x;z];y]]%*
\ Applying the definition of %3reverse%* to the LHS of (1) yields:
.PT2
\←   (2)   %3append[reverse[y];append[reverse[z];concat[x;( )]]]%* 
.PT2
\ Applying the definition of %3append%* to the RHS of (1) yields:
.PT2
\←   (3)   %3reverse[concat[x;append[z;y]]]%*
.PT2
\ Applying the definition of %3reverse%* to (3) yields:
.PT2
\←   (4)   %3append[reverse[append[z;y]];concat[x;( )]]%*
.PT2
\ Using our induction hypothesis on (4) gives:
.PT2
\←   (5)   %3append[append[reverse[y];reverse[z]];concat[x;( )]]%*
.PT2
\ At this point we must establish that    (2) = (5).
\ But this is just an instance of the associativity of %3append%*:
.pt2
\←%3append[x;append[y;z]] = append[append[x;y];z]%*  
.pt2
.END

The structure of the proof is analogous to proofs by mathematical 
induction in elementary number theory. The ability to perform such proofs
is a direct consequence of our careful definition of data structures.
Examination of the proof will show that there is a close relationship
between what we are inducting on in the proof and what  we are recurring on
during the evaluation of the  expressions. A program
written by Boyer and Moore has been reasonably successful in generating
proofs like the above by exploiting this relationship. See
⊗↑[Boy#75]↑ or ⊗↑[Moor#75b]↑.⊗↓There is also a formal system 
 based on a typed %9λ%1-calculus
which has had significant success in proving properies of programs. 
⊗↑[LCF#72]↑,#⊗↑[New#75]↑.
More recently ⊗↑[Car#76]↑ has developed a  formal system including
rules of inference, a proof checker, and a viable programming language
which is based on a "typed LISP".← 


.CENT(Problems)

1.##Prove the associativity of %3append%*.
.NL
2.##Analysis of the above proof shows frequent use of other results for LISP
functions. Fill in the details. Investigate the possibility of formalizing
this proof, showing what axioms are needed.
.NL
3.##Show the equivalence of %3fact%* ({yon(P20)}) and %3fact%41%1 ({yon(P21)}).
.NL
4.##Show the equivalence of %3length%* and %3length%41%1 ({yon(P19)}).
.NL
5.##Using the definition of %3reverse%*, given on {yon(P16)}, prove:
.BOXA
←%3reverse[reverse[x]] = x%* 

.END